help-gnu-emacs
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: All Possible Combinations


From: B. T. Raven
Subject: Re: All Possible Combinations
Date: Wed, 03 Jun 2009 08:36:00 -0500
User-agent: Thunderbird 2.0.0.21 (Windows/20090302)

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




reply via email to

[Prev in Thread] Current Thread [Next in Thread]