all possible combinations

[Jack Diederich]

On Wed, Jul 13, 2005 at 05:07:33PM +0100, Duncan Smith wrote:
> rbt wrote:
> > On Wed, 2005-07-13 at 11:09 -0400, rbt wrote:
> > 
> >>On Wed, 2005-07-13 at 10:21 -0400, rbt wrote:
> >>
> >>>Say I have a list that has 3 letters in it:
> >>>
> >>>['a', 'b', 'c']
> >>>
> >>>I want to print all the possible 4 digit combinations of those 3
> >>>letters:
> >>>
> >>>4^3 = 64
> >>>
> >>>aaaa
> >>>abaa
> >>>aaba
> >>>aaab
> >>>acaa
> >>>aaca
> >>>aaac
> >>>...
> >>>
> >>>What is the most efficient way to do this? 
> >>
> >>Expanding this to 4^4 (256) to test the random.sample function produces
> >>interesting results. It never finds more than 24 combinations out of the
> >>possible 256. This leads to the question... how 'random' is sample ;)
> >>
> >>Try it for yourselves:
> >>
> >>test = list('1234')
> >>
> >>combinations = []
> >>while 1:
> >>    combo = random.sample(test, 4)
> >>    possibility = ''.join(combo)
> >>    if possibility not in combinations:
> >>        print possibility    
> >>        combinations.append(possibility)
> >>        continue
> >>    else:
> >>        continue
> >>
> > 
> > 
> > Someone pointed out off-list that this is doing permutation, not
> > combination. Is there a way to make random.sample to do combinations?
> > 
> Probably not in any sensible way.  But what you list in your original
> post are not distinct combinations.  e.g. abaa and aaba are both 3 a's
> and 1 b.  Maybe you mean that order does matter (and you're actually
> looking for all distinct permutations of all combinations)?
> 
This is called a cartesian product, and the easiest way is to do

import probstat # probstat.sourceforge.net
letters = list('abcd')
for (guys) in probstat.Cartesian([letters] * 4):
  print ''.join(guys)

It's a C module I wrote to do this stuff a few years ago, still compiles
and runs just fine (at least on linux).

-jackdied