From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: =?ISO-8859-1?Q?Nordl=F6w?= Newsgroups: gmane.emacs.help Subject: Re: All Possible Combinations Date: Wed, 3 Jun 2009 23:08:29 -0700 (PDT) Organization: http://groups.google.com Message-ID: References: <778c22e3-3233-4cec-899e-c9f77208155a@z14g2000yqa.googlegroups.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1244148209 3494 80.91.229.12 (4 Jun 2009 20:43:29 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 4 Jun 2009 20:43:29 +0000 (UTC) To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Thu Jun 04 22:43:26 2009 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1MCJmX-0003m1-FX for geh-help-gnu-emacs@m.gmane.org; Thu, 04 Jun 2009 22:43:25 +0200 Original-Received: from localhost ([127.0.0.1]:40072 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1MCJmX-0005C8-0u for geh-help-gnu-emacs@m.gmane.org; Thu, 04 Jun 2009 16:43:25 -0400 Original-Path: news.stanford.edu!headwall.stanford.edu!news.glorb.com!news2.glorb.com!postnews.google.com!q16g2000yqg.googlegroups.com!not-for-mail Original-Newsgroups: gnu.emacs.help Original-Lines: 67 Original-NNTP-Posting-Host: 81.170.250.228 Original-X-Trace: posting.google.com 1244095709 3503 127.0.0.1 (4 Jun 2009 06:08:29 GMT) Original-X-Complaints-To: groups-abuse@google.com Original-NNTP-Posting-Date: Thu, 4 Jun 2009 06:08:29 +0000 (UTC) Complaints-To: groups-abuse@google.com Injection-Info: q16g2000yqg.googlegroups.com; posting-host=81.170.250.228; posting-account=ytJKAgoAAAA1tg4ScoRszebXiIldA5vg User-Agent: G2/1.0 X-HTTP-UserAgent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1pre) Gecko/20090526 Ubuntu/9.04 (jaunty) Shiretoko/3.5pre, gzip(gfe), gzip(gfe) Original-Xref: news.stanford.edu gnu.emacs.help:169708 X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.help:64938 Archived-At: On Jun 3, 8:50=A0pm, Marc Tfardy wrote: > Nordl=F6w 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) > > =A0 "Generate a listing of all the possible combinations of the > > elements in the sequence N. Time-Complexity is N!" > > =A0 (let (all) > > =A0 =A0 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=3D485066 > > (defun permutations (bag) > =A0 =A0"Return a list of all the permutations of the input." > =A0 =A0;; If the input is nil, there is only one permutation: > =A0 =A0;; nil itself > =A0 =A0(if (null bag) > =A0 =A0 =A0 =A0'(()) > =A0 =A0 =A0 =A0;; Otherwise, take an element, e, out of the bag. > =A0 =A0 =A0 =A0;; Generate all permutations of the remaining elements, > =A0 =A0 =A0 =A0;; And add e to the front of each of these. > =A0 =A0 =A0 =A0;; Do this for all possible e to generate all permutations= . > =A0 =A0 =A0 =A0(mapcan #'(lambda (e) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(mapcar #'(lambda (p) (cons e p)) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(permutations > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(remove e bag = :count 1)))) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0bag))) > > 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