All Possible Combinations

All Possible Combinations

[Nordlöw]

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.

Thanks in advance,
Nordlöw

Re: All Possible Combinations

[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__

Re: All Possible Combinations

[Lennart Borgman]

On Wed, Jun 3, 2009 at 11:09 AM, Nordlöw <per.nordlow@gmail.com> wrote:
> 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.

Would not that require building a stack to keep track of state just as
recursion would do internally?

Re: All Possible Combinations

[B. T. Raven]

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

Re: All Possible Combinations

[Marc Tfardy]

Nordlöw schrieb:
> 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.

Here you find working common lisp version:
http://www.perlmonks.org/?node_id=485066

(defun permutations (bag)
   "Return a list of all the permutations of the input."
   ;; If the input is nil, there is only one permutation:
   ;; nil itself
   (if (null bag)
       '(())
       ;; Otherwise, take an element, e, out of the bag.
       ;; Generate all permutations of the remaining elements,
       ;; And add e to the front of each of these.
       ;; Do this for all possible e to generate all permutations.
       (mapcan #'(lambda (e)
                   (mapcar #'(lambda (p) (cons e p))
                           (permutations
                             (remove e bag :count 1))))
               bag)))


Now replace 'remove' with 'remove*' and this works in emacs lisp, too.

regards
Marc

Re: All Possible Combinations

[Nordlöw]

On Jun 3, 8:50 pm, Marc Tfardy <tfar...@very-tfardol.com> wrote:
> Nordlöw schrieb:
>
>
>
> > 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.
>
> Here you find working common lisp version:http://www.perlmonks.org/?node_id=485066
>
> (defun permutations (bag)
>    "Return a list of all the permutations of the input."
>    ;; If the input is nil, there is only one permutation:
>    ;; nil itself
>    (if (null bag)
>        '(())
>        ;; Otherwise, take an element, e, out of the bag.
>        ;; Generate all permutations of the remaining elements,
>        ;; And add e to the front of each of these.
>        ;; Do this for all possible e to generate all permutations.
>        (mapcan #'(lambda (e)
>                    (mapcar #'(lambda (p) (cons e p))
>                            (permutations
>                              (remove e bag :count 1))))
>                bag)))
>
> Now replace 'remove' with 'remove*' and this works in emacs lisp, too.
>
> regards
> Marc

This gives the error: "e is undefined" in Emacs:

(defun all-combinations-gen (bag)
  "Return a list of all the permutations of the input."
  (if (null bag) '(())
    ;; Otherwise, take an element, e, out of the bag.
    ;; Generate all permutations of the remaining elements,
    ;; And add e to the front of each of these.
    ;; Do this for all possible e to generate all permutations.
    (mapcan #'(lambda (e)
                (mapcar #'(lambda (p) (cons e p))
                        (permutations
                         (remove* e bag :count 1))))
            bag)))

(all-combinations-gen '(a b c))

/Per

Re: All Possible Combinations

[Marc Tfardy]

Nordlöw schrieb:
> On Jun 3, 8:50 pm, Marc Tfardy <tfar...@very-tfardol.com> wrote:
>> Nordlöw schrieb:
>>
>>
>>
>>> 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.
>> Here you find working common lisp version:http://www.perlmonks.org/?node_id=485066
>>
>> (defun permutations (bag)
>>    "Return a list of all the permutations of the input."
>>    ;; If the input is nil, there is only one permutation:
>>    ;; nil itself
>>    (if (null bag)
>>        '(())
>>        ;; Otherwise, take an element, e, out of the bag.
>>        ;; Generate all permutations of the remaining elements,
>>        ;; And add e to the front of each of these.
>>        ;; Do this for all possible e to generate all permutations.
>>        (mapcan #'(lambda (e)
>>                    (mapcar #'(lambda (p) (cons e p))
>>                            (permutations
>>                              (remove e bag :count 1))))
>>                bag)))
>>
>> Now replace 'remove' with 'remove*' and this works in emacs lisp, too.
>>
>> regards
>> Marc
> 
> This gives the error: "e is undefined" in Emacs:
> 
> (defun all-combinations-gen (bag)
>   "Return a list of all the permutations of the input."
>   (if (null bag) '(())
>     ;; Otherwise, take an element, e, out of the bag.
>     ;; Generate all permutations of the remaining elements,
>     ;; And add e to the front of each of these.
>     ;; Do this for all possible e to generate all permutations.
>     (mapcan #'(lambda (e)
>                 (mapcar #'(lambda (p) (cons e p))
>                         (permutations
>                          (remove* e bag :count 1))))
>             bag)))
> 
> (all-combinations-gen '(a b c))

Check all again, please. I've tested this code just now once again
and here is everything working fine. I get:


(all-combinations-gen '(a b c))
((a b c) (a c b) (b a c) (b c a) (c a b) (c b a))

regards
Marc

Re: All Possible Combinations

[B. T. Raven]

Marc Tfardy wrote:
> Nordlöw schrieb:
>> On Jun 3, 8:50 pm, Marc Tfardy <tfar...@very-tfardol.com> wrote:
>>> Nordlöw schrieb:
>>>
>>>
>>>
>>>> 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.
>>> Here you find working common lisp 
>>> version:http://www.perlmonks.org/?node_id=485066
>>>
>>> (defun permutations (bag)
>>>    "Return a list of all the permutations of the input."
>>>    ;; If the input is nil, there is only one permutation:
>>>    ;; nil itself
>>>    (if (null bag)
>>>        '(())
>>>        ;; Otherwise, take an element, e, out of the bag.
>>>        ;; Generate all permutations of the remaining elements,
>>>        ;; And add e to the front of each of these.
>>>        ;; Do this for all possible e to generate all permutations.
>>>        (mapcan #'(lambda (e)
>>>                    (mapcar #'(lambda (p) (cons e p))
>>>                            (permutations
>>>                              (remove e bag :count 1))))
>>>                bag)))
>>>
>>> Now replace 'remove' with 'remove*' and this works in emacs lisp, too.
>>>
>>> regards
>>> Marc
>>
>> This gives the error: "e is undefined" in Emacs:
>>
>> (defun all-combinations-gen (bag)
>>   "Return a list of all the permutations of the input."
>>   (if (null bag) '(())
>>     ;; Otherwise, take an element, e, out of the bag.
>>     ;; Generate all permutations of the remaining elements,
>>     ;; And add e to the front of each of these.
>>     ;; Do this for all possible e to generate all permutations.
>>     (mapcan #'(lambda (e)
>>                 (mapcar #'(lambda (p) (cons e p))
>>                         (permutations
>>                          (remove* e bag :count 1))))
>>             bag)))
>>
>> (all-combinations-gen '(a b c))
> 
> Check all again, please. I've tested this code just now once again
> and here is everything working fine. I get:
> 
> 
> (all-combinations-gen '(a b c))
> ((a b c) (a c b) (b a c) (b c a) (c a b) (c b a))
> 
> regards
> Marc
> 

Also doesn't quite work here:

Backtrace:

Debugger entered--Lisp error: (void-function permutations)
   (permutations (remove* e bag :count 1))
   (mapcar (function (lambda ... ...)) (permutations (remove* e bag 
:count 1)))
...

I'm assuming that all I need is M-x load-library cl to get mapcan and 
remove*
I tried on ver 22 but not 23

Okay, finally comes the light: defun has to be named either 
all-combinations-gen or permutations. Works if that renaming is made 
consistent. Should be permutations, since there is only one combination 
of elements a,b,c taken three at a time. All permutations collapse into 
one combination.

Ed

Re: All Possible Combinations

[Thierry Volpiatto]

Marc Tfardy <tfardol@very-tfardol.com> writes:

> Nordlöw schrieb:
>> On Jun 3, 8:50 pm, Marc Tfardy <tfar...@very-tfardol.com> wrote:
>>> Nordlöw schrieb:
>>>
>>>
>>>
>>>> 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.
>>> Here you find working common lisp version:http://www.perlmonks.org/?node_id=485066
>>>
>>> (defun permutations (bag)
>>>    "Return a list of all the permutations of the input."
>>>    ;; If the input is nil, there is only one permutation:
>>>    ;; nil itself
>>>    (if (null bag)
>>>        '(())
>>>        ;; Otherwise, take an element, e, out of the bag.
>>>        ;; Generate all permutations of the remaining elements,
>>>        ;; And add e to the front of each of these.
>>>        ;; Do this for all possible e to generate all permutations.
>>>        (mapcan #'(lambda (e)
>>>                    (mapcar #'(lambda (p) (cons e p))
>>>                            (permutations
>>>                              (remove e bag :count 1))))
>>>                bag)))
>>>
>>> Now replace 'remove' with 'remove*' and this works in emacs lisp, too.
>>>
>>> regards
>>> Marc
>>
>> This gives the error: "e is undefined" in Emacs:
>>
>> (defun all-combinations-gen (bag)
>>   "Return a list of all the permutations of the input."
>>   (if (null bag) '(())
>>     ;; Otherwise, take an element, e, out of the bag.
>>     ;; Generate all permutations of the remaining elements,
>>     ;; And add e to the front of each of these.
>>     ;; Do this for all possible e to generate all permutations.
>>     (mapcan #'(lambda (e)
>>                 (mapcar #'(lambda (p) (cons e p))
>>                         (permutations
>>                          (remove* e bag :count 1))))
>>             bag)))
>>
>> (all-combinations-gen '(a b c))
>
> Check all again, please. I've tested this code just now once again
> and here is everything working fine. I get:
>
>
> (all-combinations-gen '(a b c))
> ((a b c) (a c b) (b a c) (b c a) (c a b) (c b a))

Work fine for me too, very nice code :-)
Would be nice if the same function accept an extra arg to specify the
number of elements of the combinations we want, something like:

(all-combinations-gen '(a b c) 2)
==> ((a b) (a c) (b c) ....)

Don't find yet how to do that ...

-- 
A + Thierry Volpiatto
Location: Saint-Cyr-Sur-Mer - France