all possible combinations

[Duncan Smith]

Jack Diederich wrote:
> 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

Yep.  probstat also ran on Windows the last time I used it :-).

Duncan