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?

 

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

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

The CPU

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

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

 

[Steven D'Aprano]

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?

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.

 

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

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

 

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

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?

 

[Steven D'Aprano]

The CPU

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]

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

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.

 

[Duncan Smith]

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

There are only 24 possible lists that random.sample(test, 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

 

[Steven D'Aprano]

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.

 

[Duncan Smith]

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

Duncan

 

[Christopher Subich]

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

sample(population,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]

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

 

[Duncan Smith]

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

 

[George Sakkis]

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

It's actually 3^4 = 81 (3 candidates/choice ** 4 choices)

aaaa
abaa
aaba
aaab
acaa
aaca
aaac
...

What is the most efficient way to do this?

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 iterPermutations(num, seq):
if num:
for rest in iterPermutations(num-1, seq):
for item in seq:
yield rest + [item]
else:
yield []


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


George

 

[Thomas Bartkus]

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

It's actually 3^4 = 81 (3 candidates/choice ** 4 choices)

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.Letter, 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]

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

Should be 3**4 = 81.

aaaa
abaa
aaba
aaab
acaa
aaca
aaac
...

What is the most efficient way to do this?

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

 

[John Machin]

On Wed, 13 Jul 2005 10:39:41 -0400, rbt wrote: [snip]
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. [snip]

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

That's good, since you only need combinations of "a", "b" and "c" the

"You keep using that word. I do not think it means what you think it means."

Both of you please google("define: combination")

 

[John Machin]

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

Uh-oh -- there's that word again! What you mean to say is that it never
finds more than 24 *PERMUTATIONS*.

1. google("define: permutation")
2. Consider that 24 == 4 * 3 * 2 * 1
3. RTFM("random.sample"), paying particular attention to the word "unique"

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

Instead of the utterly pointless continue/else/continue, shouldn't you
have some method (other than keyboard interrupt) of jumping off the
merry-go-round?

 

[Edvard Majakari]

"You keep using that word. I do not think it means what you think it means."

Inconceivable!

--
# Edvard Majakari Software Engineer
# PGP PUBLIC KEY available Soli Deo Gloria!

"Debugging is twice as hard as writing the code in the firstplace. Therefore,
if you write the code as cleverly as possible, you are, by definition,
not smart enough to debug it." -- Brian W. Kernighan

 

[Thorsten Kampe]

* Thomas Bartkus (2005-07-13 20:20 +0100)

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

It's actually 3^4 = 81 (3 candidates/choice ** 4 choices)

Yes. You get a cigar!

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

In set theory it's called "cartesian product" while in combinatorics
it's called "variation with repetition". There is some "die-hard"
terminology confusion about permutations, combinations and variations
(see [1] for example).

(luckily at least most of the Python "officials" (GvR and Frederik
Lundh) seem to agree about this terminology)

Thorsten

[1] http://groups-beta.google.com/group/comp.lang.python/msg/dea80dec0192eda6?hl=en&

 

[Steven D'Aprano]

"You keep using that word. I do not think it means what you think it means."

Both of you please google("define: combination")

Combination: "a coordinated sequence of chess moves".

"An option position that is effected by either a purchase of two long
positions or two short positions. The investor purchases a call and a put
(or sells a call and a put) with different expiration dates and/or
different strike prices."

Or perhaps "in Scheme, a function call, consisting of a function name and
arguments written within parentheses."

Yes, mathematically the definition of combination includes that order does
not matter. But that certainly isn't the case in common English. Now,
John, given the tone of the posts you are complaining about, do you think
I was using combination in the precise mathematical sense, or the common
English sense?

(Hint: the very first definition Google finds is "a collection of things
that have been combined; an assemblage of separate parts or qualities ".
Not a word there about order mattering or not.)