Re: All Possible Combinations

[Marc Tfardy <tfardol@very-tfardol.com>]

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