Re: All Possible Combinations

["B. T. Raven" <nihil@nihilo.net>]

Pascal J. Bourguignon wrote:
> 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.

Both permutations and combinations can deal with n things taken r at a 
time where r can equal n:

nPr =  n! / (n-r)!


nCr = n! / (n-r)! r!

So in general (at least when r /= 1) the number of resultant sets is 
smaller with nCr



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