From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: pjb@informatimago.com (Pascal J. Bourguignon) Newsgroups: gmane.emacs.help Subject: Re: All Possible Combinations Date: Wed, 03 Jun 2009 11:53:48 +0200 Organization: Anevia SAS Message-ID: <7chbyxprrn.fsf@pbourguignon.anevia.com> 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: 8bit X-Trace: ger.gmane.org 1244025657 17421 80.91.229.12 (3 Jun 2009 10:40:57 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 3 Jun 2009 10:40:57 +0000 (UTC) To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Wed Jun 03 12:40:55 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 1MBntn-0007Az-Qg for geh-help-gnu-emacs@m.gmane.org; Wed, 03 Jun 2009 12:40:48 +0200 Original-Received: from localhost ([127.0.0.1]:52263 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1MBntn-0005w0-7W for geh-help-gnu-emacs@m.gmane.org; Wed, 03 Jun 2009 06:40:47 -0400 Original-Path: news.stanford.edu!headwall.stanford.edu!newsfeed.esat.net!feeder.news.heanet.ie!feeder.erje.net!de-l.enfer-du-nord.net!usenet-fr.net!proxad.net!feeder1-2.proxad.net!cleanfeed1-a.proxad.net!nnrp12-2.free.fr!not-for-mail Original-Newsgroups: gnu.emacs.help Face: iVBORw0KGgoAAAANSUhEUgAAADAAAAAwAQMAAABtzGvEAAAABlBMVEUAAAD///+l2Z/dAAAA oElEQVR4nK3OsRHCMAwF0O8YQufUNIQRGIAja9CxSA55AxZgFO4coMgYrEDDQZWPIlNAjwq9 033pbOBPtbXuB6PKNBn5gZkhGa86Z4x2wE67O+06WxGD/HCOGR0deY3f9Ijwwt7rNGNf6Oac l/GuZTF1wFGKiYYHKSFAkjIo1b6sCYS1sVmFhhhahKQssRjRT90ITWUk6vvK3RsPGs+M1RuR mV+hO/VvFAAAAABJRU5ErkJggg== X-Accept-Language: fr, es, en X-Disabled: X-No-Archive: no User-Agent: Gnus/5.101 (Gnus v5.10.10) Emacs/22.2 (gnu/linux) Cancel-Lock: sha1:NTUwZGQxY2JkYTdiOWU3ZmU2YWFjMjNiOGExMThiYmYxZTY4MTNkMA== Original-Lines: 50 Original-NNTP-Posting-Date: 03 Jun 2009 11:53:48 MEST Original-NNTP-Posting-Host: 88.170.236.224 Original-X-Trace: 1244022828 news-2.free.fr 28334 88.170.236.224:57175 Original-X-Complaints-To: abuse@proxad.net Original-Xref: news.stanford.edu gnu.emacs.help:169685 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:64917 Archived-At: Nordlöw writes: > 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. It's called permutations. Combinations are when you take a smaller number of elements amongst the set. Now notice that (permutations '()) = (()) that is, the set of permutations of the empty set contains only the empty set (there's no other way to order no elements) and notice that (permutations '(a)) = ((a)) (there's only one way to order one element). Now, knowing that (permutations '(a)) = ((a)) How can you compute (permutations '(b a))? That is, how many ways can you put b in the permutations of (a), for example, in (a)? Yes, there's two ways: before or after a: (b a) or (a b). So now we know that (permutations '(b a)) = ((b a) (a b)) Then, how can you compute (permutations '(c b a))? That is, how many ways can you put c in the permutations of (b a), for example, in (a b)? ... So now we know that (permutations '(x ...)) = ((x ...) ... (... x)) Then, how can you compute (permutations '(y x ...))? That is, how many ways can you put y in the permutations of (x ...), for example, in (... x)? -- __Pascal Bourguignon__