Re: All Possible Combinations

[pjb@informatimago.com (Pascal J. Bourguignon)]

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__