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)?