From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: "B. T. Raven" Newsgroups: gmane.emacs.help Subject: Re: All Possible Combinations Date: Thu, 04 Jun 2009 11:25:22 -0500 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; format=flowed Content-Transfer-Encoding: 8bit X-Trace: ger.gmane.org 1244148640 4755 80.91.229.12 (4 Jun 2009 20:50:40 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 4 Jun 2009 20:50:40 +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:50:38 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 1MCJtV-0006bq-1i for geh-help-gnu-emacs@m.gmane.org; Thu, 04 Jun 2009 22:50:37 +0200 Original-Received: from localhost ([127.0.0.1]:51761 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1MCJtR-0004CR-Gy for geh-help-gnu-emacs@m.gmane.org; Thu, 04 Jun 2009 16:50:33 -0400 Original-Path: news.stanford.edu!newsfeed.stanford.edu!postnews.google.com!news2.google.com!npeer03.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!nx01.iad01.newshosting.com!newshosting.com!216.196.98.140.MISMATCH!border1.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!backlog2.nntp.dca.giganews.com!nntp.sysmatrix.net!news.sysmatrix.net.POSTED!not-for-mail Original-NNTP-Posting-Date: Thu, 04 Jun 2009 11:24:55 -0500 User-Agent: Thunderbird 2.0.0.21 (Windows/20090302) Original-Newsgroups: gnu.emacs.help In-Reply-To: Original-Lines: 94 X-Usenet-Provider: http://www.giganews.com Original-NNTP-Posting-Host: 12.73.129.134 Original-X-Trace: sv3-OKwv4pfGkncAyUtavv8YfQ+BCmROt6YAjOXH8BJeCaCKYgNUUGxHVUrJyRwvZhyp4Mej8R56hnEMI+o!feQqTHGY1brtF6dJ/E6gFpghVp6oqOg4K4Mlk/bkeKWzFYZu1Mn92iqAKiRDVYtdd+IrgfaX6c72!2C4j/DquoXBd477+l2KlnUp9DIkPqxE= Original-X-Complaints-To: abuse@sysmatrix.net X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.39 X-Original-Bytes: 4557 Original-Xref: news.stanford.edu gnu.emacs.help:169717 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:64946 Archived-At: Marc Tfardy wrote: > Nordlöw schrieb: >> On Jun 3, 8:50 pm, Marc Tfardy 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