[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: All Possible Combinations
From: |
Marc Tfardy |
Subject: |
Re: All Possible Combinations |
Date: |
Wed, 03 Jun 2009 20:50:00 +0200 |
User-agent: |
Thunderbird 2.0.0.21 (Windows/20090302) |
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