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: Wed, 03 Jun 2009 08:36:00 -0500 Message-ID: References: <778c22e3-3233-4cec-899e-c9f77208155a@z14g2000yqa.googlegroups.com> <7chbyxprrn.fsf@pbourguignon.anevia.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 1244036448 19911 80.91.229.12 (3 Jun 2009 13:40:48 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 3 Jun 2009 13:40:48 +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 15:40:42 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 1MBqht-00051R-KV for geh-help-gnu-emacs@m.gmane.org; Wed, 03 Jun 2009 15:40:41 +0200 Original-Received: from localhost ([127.0.0.1]:43177 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1MBqhs-0003Bu-N9 for geh-help-gnu-emacs@m.gmane.org; Wed, 03 Jun 2009 09:40:40 -0400 Original-Path: news.stanford.edu!newsfeed.stanford.edu!postnews.google.com!news1.google.com!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: Wed, 03 Jun 2009 08:35:32 -0500 User-Agent: Thunderbird 2.0.0.21 (Windows/20090302) Original-Newsgroups: gnu.emacs.help In-Reply-To: <7chbyxprrn.fsf@pbourguignon.anevia.com> Original-Lines: 63 X-Usenet-Provider: http://www.giganews.com Original-NNTP-Posting-Host: 12.73.132.212 Original-X-Trace: sv3-obJPeCQg/22SRJeWTaviMSyX4/8+JAgKJzP6fwo6+86l3W1pBn+Z0bsC2OIfXs25GAoRJbhK4LRPF0L!8aB1Qs+28pU+Mk29G7Gh6BM7AJPr4lipOIoIDwWyPKLjeoYNgEBnPhDnQVbFknBR0D8WhV0igPcI!zapovftL0wZoPfJKTvhRxM9DMvhC0pM= 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: 3268 Original-Xref: news.stanford.edu gnu.emacs.help:169695 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:64925 Archived-At: Pascal J. Bourguignon wrote: > 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. Both permutations and combinations can deal with n things taken r at a time where r can equal n: nPr = n! / (n-r)! nCr = n! / (n-r)! r! So in general (at least when r /= 1) the number of resultant sets is smaller with nCr > > 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)? > >