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