[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: All Possible Combinations
From: |
Pascal J. Bourguignon |
Subject: |
Re: All Possible Combinations |
Date: |
Wed, 03 Jun 2009 11:53:48 +0200 |
User-agent: |
Gnus/5.101 (Gnus v5.10.10) Emacs/22.2 (gnu/linux) |
Nordlöw <per.nordlow@gmail.com> writes:
> Hey!
>
> I want a function that generates all possible combinations (ordering)
> of the elements in a list (or sequence if possible). Here is my
> mockup:
>
> (defun all-combinations (n)
> "Generate a listing of all the possible combinations of the
> elements in the sequence N. Time-Complexity is N!"
> (let (all)
> all))
>
> For example (all-combinations '(a b c)) should return '((a b c) (a c
> b) (b a c) (b c a) (c a b) (c b a))
>
> Has somebody written such a function, preferrably in an iterative
> rather than recursive way.
It's called permutations. Combinations are when you take a smaller
number of elements amongst the set.
Now notice that (permutations '()) = (())
that is, the set of permutations of the empty set contains only the
empty set (there's no other way to order no elements)
and notice that (permutations '(a)) = ((a))
(there's only one way to order one element).
Now, knowing that (permutations '(a)) = ((a))
How can you compute (permutations '(b a))?
That is, how many ways can you put b in the permutations of (a), for example,
in (a)?
Yes, there's two ways: before or after a: (b a) or (a b).
So now we know that (permutations '(b a)) = ((b a) (a b))
Then, how can you compute (permutations '(c b a))?
That is, how many ways can you put c in the permutations of (b a), for example,
in (a b)?
...
So now we know that (permutations '(x ...)) = ((x ...) ... (... x))
Then, how can you compute (permutations '(y x ...))?
That is, how many ways can you put y in the permutations of (x ...), for
example, in (... x)?
--
__Pascal Bourguignon__