all possible combinations

[rbt]

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?

[Steven D'Aprano]

Re: all possible combinations

On Wed, 13 Jul 2005 10:21:19 -0400, rbt wrote:
[color=blue]
> 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?[/color]

Efficient for who? The user? The programmer? The computer? Efficient use
of speed or memory or development time?

If you want the fastest runtime efficiency, a lookup table of
pre-calculated values. That is an O(1) operation, and you don't get any
faster than that.

If you expect to extend the program to arbitrary lists, pre-calculation
isn't practical, so you need an algorithm to calculate permutations (order
matters) or combinations (order doesn't matter).

If you tell us what you need, I'm sure somebody will be able to help meet
those needs. Otherwise, we're just guessing what you want.



--
Steven.

[rbt]

Re: all possible combinations

On Thu, 2005-07-14 at 00:47 +1000, Steven D'Aprano wrote:[color=blue]
> On Wed, 13 Jul 2005 10:21:19 -0400, rbt wrote:
>[color=green]
> > 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?[/color]
>
> Efficient for who? The user? The programmer? The computer? Efficient use
> of speed or memory or development time?[/color]

The CPU
[color=blue]
>
> If you want the fastest runtime efficiency, a lookup table of
> pre-calculated values. That is an O(1) operation, and you don't get any
> faster than that.
>
> If you expect to extend the program to arbitrary lists, pre-calculation
> isn't practical, so you need an algorithm to calculate permutations (order
> matters) or combinations (order doesn't matter).[/color]

My list is not arbitrary. I'm looking for all 'combinations' as I
originally posted. Order does not matter to me... just all
possibilities.

[rbt]

Re: all possible combinations

On Wed, 2005-07-13 at 10:21 -0400, rbt wrote:[color=blue]
> 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?[/color]

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(t est, 4)
possibility = ''.join(combo)
if possibility not in combinations:
print possibility
combinations.ap pend(possibilit y)
continue
else:
continue

[Steven D'Aprano]

Re: all possible combinations

On Wed, 13 Jul 2005 10:39:41 -0400, rbt wrote:
[color=blue][color=green][color=darkred]
>> > What is the most efficient way to do this?[/color]
>>
>> Efficient for who? The user? The programmer? The computer? Efficient use
>> of speed or memory or development time?[/color]
>
> The CPU[/color]

Ah, then that's easy. Sit down with pencil and paper, write out all 64
combinations yourself, and then type them into a Python list. Then you can
access any one of those combinations with a single call.

A lookup table is the fastest possible way for the CPU to give you the
answer you want.

[snip][color=blue]
> My list is not arbitrary. I'm looking for all 'combinations' as I
> originally posted. Order does not matter to me... just all possibilities.[/color]

That's good, since you only need combinations of "a", "b" and "c" the
lookup table is quite small and manageable. I was worried that you might
have wanted to apply your function to any set of items.


--
Steven.

[rbt]

Re: all possible combinations

On Wed, 2005-07-13 at 11:09 -0400, rbt wrote:[color=blue]
> On Wed, 2005-07-13 at 10:21 -0400, rbt wrote:[color=green]
> > 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?[/color]
>
> 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(t est, 4)
> possibility = ''.join(combo)
> if possibility not in combinations:
> print possibility
> combinations.ap pend(possibilit y)
> continue
> else:
> continue
>[/color]

Someone pointed out off-list that this is doing permutation, not
combination. Is there a way to make random.sample to do combinations?

[Steven D'Aprano]

Re: all possible combinations

On Wed, 13 Jul 2005 11:09:25 -0400, rbt wrote:
[color=blue]
> On Wed, 2005-07-13 at 10:21 -0400, rbt wrote:[color=green]
>> 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:[/color][/color]

[snip]
[color=blue]
> 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 ;)[/color]

See below.
[color=blue]
> Try it for yourselves:
>
> test = list('1234')
>
> combinations = []
> while 1:
> combo = random.sample(t est, 4)
> possibility = ''.join(combo)
> if possibility not in combinations:
> print possibility
> combinations.ap pend(possibilit y)
> continue
> else:
> continue[/color]

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

combinations = []
while 1:
combo = random.sample(t est, 4)
possibility = ''.join(combo)
if possibility not in combinations:
print possibility
combinations.ap pend(possibilit y)

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(sel f, 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.

[Duncan Smith]

Re: all possible combinations

rbt wrote:[color=blue]
> On Wed, 2005-07-13 at 10:21 -0400, rbt wrote:
>[color=green]
>>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?[/color]
>
>
> 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(t est, 4)
> possibility = ''.join(combo)
> if possibility not in combinations:
> print possibility
> combinations.ap pend(possibilit y)
> continue
> else:
> continue
>[/color]

There are only 24 possible lists that random.sample(t est, 4) can return,
corresponding to the 24 possible orderings of 4 items. i.e.
random.sample() samples without replacement. You need to sample with
replacement.

Duncan

[Duncan Smith]

Re: all possible combinations

rbt wrote:[color=blue]
> On Wed, 2005-07-13 at 11:09 -0400, rbt wrote:
>[color=green]
>>On Wed, 2005-07-13 at 10:21 -0400, rbt wrote:
>>[color=darkred]
>>>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?[/color]
>>
>>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')
>>
>>combination s = []
>>while 1:
>> combo = random.sample(t est, 4)
>> possibility = ''.join(combo)
>> if possibility not in combinations:
>> print possibility
>> combinations.ap pend(possibilit y)
>> continue
>> else:
>> continue
>>[/color]
>
>
> Someone pointed out off-list that this is doing permutation, not
> combination. Is there a way to make random.sample to do combinations?
>[/color]

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)?

Duncan

[Christopher Subich]

Re: all possible combinations

rbt wrote:[color=blue]
> 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 ;)[/color]

sample(populati on,k):
Return a k length list of unique elements chosen from the population
sequence. Used for random sampling without replacement. New in version
2.3.

Working as designed, I'd say. 4! = 24.

[Jack Diederich]

Re: all possible combinations

On Wed, Jul 13, 2005 at 05:07:33PM +0100, Duncan Smith wrote:[color=blue]
> rbt wrote:[color=green]
> > On Wed, 2005-07-13 at 11:09 -0400, rbt wrote:
> >[color=darkred]
> >>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')
> >>
> >>combination s = []
> >>while 1:
> >> combo = random.sample(t est, 4)
> >> possibility = ''.join(combo)
> >> if possibility not in combinations:
> >> print possibility
> >> combinations.ap pend(possibilit y)
> >> continue
> >> else:
> >> continue
> >>[/color]
> >
> >
> > Someone pointed out off-list that this is doing permutation, not
> > combination. Is there a way to make random.sample to do combinations?
> >[/color]
> 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)?
>[/color]
This is called a cartesian product, and the easiest way is to do

import probstat # probstat.source forge.net
letters = list('abcd')
for (guys) in probstat.Cartes ian([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

[Duncan Smith]

Re: all possible combinations

Jack Diederich wrote:[color=blue]
> On Wed, Jul 13, 2005 at 05:07:33PM +0100, Duncan Smith wrote:
>[color=green]
>>rbt wrote:
>>[color=darkred]
>>>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
>>>>interesti ng 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')
>>>>
>>>>combination s = []
>>>>while 1:
>>>> combo = random.sample(t est, 4)
>>>> possibility = ''.join(combo)
>>>> if possibility not in combinations:
>>>> print possibility
>>>> combinations.ap pend(possibilit y)
>>>> continue
>>>> else:
>>>> continue
>>>>
>>>
>>>
>>>Someone pointed out off-list that this is doing permutation, not
>>>combinatio n. Is there a way to make random.sample to do combinations?
>>>[/color]
>>
>>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)?
>>[/color]
>
> This is called a cartesian product, and the easiest way is to do
>
> import probstat # probstat.source forge.net
> letters = list('abcd')
> for (guys) in probstat.Cartes ian([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[/color]

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

Duncan

[George Sakkis]

Re: all possible combinations

"rbt" <rbt@athop1.ath .vt.edu> wrote:
[color=blue]
> 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[/color]


It's actually 3^4 = 81 (3 candidates/choice ** 4 choices)
[color=blue]
> aaaa
> abaa
> aaba
> aaab
> acaa
> aaca
> aaac
> ...
>
> What is the most efficient way to do this?[/color]


I don't know if it's *the most* efficient -- and I don't think it really matters -- but it's fast,
short and sweet:

def iterPermutation s(num, seq):
if num:
for rest in iterPermutation s(num-1, seq):
for item in seq:
yield rest + [item]
else:
yield []


for comb in iterPermutation s(4, list("abc")):
print ''.join(comb)


George

[Thomas Bartkus]

Re: all possible combinations

"George Sakkis" <gsakkis@rutger s.edu> wrote in message
news:1121277937 .a2a3097d7c150f 1b8a3f41a21a9f2 b25@teranews...[color=blue]
> "rbt" <rbt@athop1.ath .vt.edu> wrote:
>[color=green]
> > 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[/color]
>
>
> It's actually 3^4 = 81 (3 candidates/choice ** 4 choices)[/color]

Yes. You get a cigar!

Someone else (Jack Diederich) also mentioned "This is called a cartesian
product, ..."
Right again.

Now I can't help injecting that SQL is custom made for returning a cartesian
product.

Given a table called [Letters] containing a field [Letter] with (3) records
Letter = 'a', 'b', 'c'

SELECT CONCAT(t1.Lette r, t2.Letter, t3.Letter, t4.Letter)
FROM Letters As t1, Letters As t2, Letters As t3, Letters As t4

Will return those 81 combinations in an eyblink.

In order to stay on topic, you are required to call your favorite SQL engine
from Python :-)
Thomas Bartkus

[mensanator@aol.com]

Re: all possible combinations



rbt wrote:[color=blue]
> 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[/color]

Should be 3**4 = 81.
[color=blue]
>
> aaaa
> abaa
> aaba
> aaab
> acaa
> aaca
> aaac
> ...
>
> What is the most efficient way to do this?[/color]

Table t
[c]
a
b
c

Query q
SELECT t_3.c AS c1, t_2.c AS c2, t_1.c AS c3, t.c AS c4
FROM t, t AS t_1, t AS t_2, t AS t_3;

output
[c1] [c2] [c3] [c4]
a a a a
a a a b
a a a c
a a b a
a a b b
a a b c
a a c a
a a c b
a a c c
a b a a
a b a b
a b a c
a b b a
a b b b
a b b c
a b c a
a b c b
a b c c
a c a a
a c a b
a c a c
a c b a
a c b b
a c b c
a c c a
a c c b
a c c c
b a a a
b a a b
b a a c
b a b a
b a b b
b a b c
b a c a
b a c b
b a c c
b b a a
b b a b
b b a c
b b b a
b b b b
b b b c
b b c a
b b c b
b b c c
b c a a
b c a b
b c a c
b c b a
b c b b
b c b c
b c c a
b c c b
b c c c
c a a a
c a a b
c a a c
c a b a
c a b b
c a b c
c a c a
c a c b
c a c c
c b a a
c b a b
c b a c
c b b a
c b b b
c b b c
c b c a
c b c b
c b c c
c c a a
c c a b
c c a c
c c b a
c c b b
c c b c
c c c a
c c c b
c c c c
Record 81 of 81