all possible combinations

Steven D'Aprano steve at REMOVETHIScyber.com.au
Wed Jul 13 17:57:25 CEST 2005


On Wed, 13 Jul 2005 11:09:25 -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:

[snip]
 
> 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 ;)

See below.
 
> 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

That's not very efficient code. Why not just write it like this?

combinations = []
while 1:
    combo = random.sample(test, 4)
    possibility = ''.join(combo)
    if possibility not in combinations:
        print possibility    
        combinations.append(possibility)

You don't need either of the two continue statements.

But in fact, random.sample is correct.

You have four items to choose from: "1", "2", "3", "4".

If you choose them with replacement, then there are 4*4*4*4 = 256
possibilities, but that includes duplicates:

[4, 4, 4, 4] is one such possibility.

As the documentation for random.sample clearly says:

"sample(self, population, k) method of random.Random instance
    Chooses k unique random elements from a population sequence."

Notice the UNIQUE part? You should have realised that just by looking at
the strings as they were printed. None of them have duplicated digits.

Sampling WITHOUT replacement gives 4*3*2*1 = 24 possibilities, exactly as
your code produces.

-- 
Steven.




More information about the Python-list mailing list