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]

On Wed, 13 Jul 2005 10:21:19 -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?

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]

On Thu, 2005-07-14 at 00:47 +1000, Steven D'Aprano wrote:

On Wed, 13 Jul 2005 10:21:19 -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?
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.

[rbt]

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

[Steven D'Aprano]

On Wed, 13 Jul 2005 10:39:41 -0400, rbt wrote:

> 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

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

[rbt]

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?

[Steven D'Aprano]

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.

[Duncan Smith]

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

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

[Duncan Smith]

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

Duncan

[Christopher Subich]

rbt wrote:

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, 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

[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

[George Sakkis]

"rbt" <rb*@athop1.ath.vt.edu> 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

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]

"George Sakkis" <gs*****@rutgers.edu> wrote in message
news:1121277937.a2a3097d7c150f1b8a3f41a21a9f2b25@t eranews...

"rbt" <rb*@athop1.ath.vt.edu> 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

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]

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
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]

Steven D'Aprano wrote:

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]

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

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]

John Machin <sj******@lexicon.net> writes:

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

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)

"George Sakkis" <gs*****@rutgers.edu> wrote in message
news:1121277937.a2a3097d7c150f1b8a3f41a21a9f2b25@t eranews...

"rbt" <rb*@athop1.ath.vt.edu> 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

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/...192eda6?hl=en&

[Steven D'Aprano]

On Thu, 14 Jul 2005 08:49:05 +1000, John Machin wrote:

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

[John Machin]

Steven D'Aprano wrote:

On Thu, 14 Jul 2005 08:49:05 +1000, John Machin wrote:

"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,

Wrong -- no complaint. Another quote: "It's a joke, Joyce!"
do you think
I was using combination in the precise mathematical sense, or the common
English sense?
As in "Please don't get your combinations in a twist?"?

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

[rbt]

Thanks to all who were helpful... some of you guys are too harsh and
cynical. Here's what I came up with. I believe it's a proper
combination, but I'm sure someone will point out that I'm wrong ;)

groups =[list('abc'),list('abc'),list('abc'),list('abc')]

already = []

while 1:

LIST = []

for g in groups:
sample = random.sample(g, 1)
LIST.append(sample[0])

STRING = ''.join(LIST)
if STRING not in already:
print STRING
already.append(STRING)
if len(already) == 81:
break

On Thu, 2005-07-14 at 23:18 +1000, John Machin wrote:

Steven D'Aprano wrote:

On Thu, 14 Jul 2005 08:49:05 +1000, John Machin wrote:

"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,

Wrong -- no complaint. Another quote: "It's a joke, Joyce!"

do you think
I was using combination in the precise mathematical sense, or the common
English sense?

As in "Please don't get your combinations in a twist?"?

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

[Paul Rubin]

rbt <rb*@athop1.ath.vt.edu> writes:

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:

for i in xrange(81):
print ''.join(['abcd'[j]
for j in [(i//d)%3 for d in (27,9,3,1)]])

[Rocco Moretti]

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:

When I have occasion to do an iteration of iterations, I either use
recursion (already posted) or use an accumulator type loop:

items = ['a','b','c']
accume = [[],]

for pos in range(4):
old_accume, accume = accume, []
for comb in old_accume:
for item in items:
accume.append(comb + [item])

accume = [''.join(x) for x in accume]
print accume

['aaaa', 'aaab', 'aaac', 'aaba', 'aabb', 'aabc', 'aaca', 'aacb', 'aacc',
'abaa', 'abab', 'abac', 'abba', 'abbb', 'abbc', 'abca', 'abcb', 'abcc',
'acaa', 'acab', 'acac', 'acba', 'acbb', 'acbc', 'acca', 'accb', 'accc',
'baaa', 'baab', 'baac', 'baba', 'babb', 'babc', 'baca', 'bacb', 'bacc',
'bbaa', 'bbab', 'bbac', 'bbba', 'bbbb', 'bbbc', 'bbca', 'bbcb', 'bbcc',
'bcaa', 'bcab', 'bcac', 'bcba', 'bcbb', 'bcbc', 'bcca', 'bccb', 'bccc',
'caaa', 'caab', 'caac', 'caba', 'cabb', 'cabc', 'caca', 'cacb', 'cacc',
'cbaa', 'cbab', 'cbac', 'cbba', 'cbbb', 'cbbc', 'cbca', 'cbcb', 'cbcc',
'ccaa', 'ccab', 'ccac', 'ccba', 'ccbb', 'ccbc', 'ccca', 'cccb', 'cccc']

Optimize as you see fit.

[William Park]

rbt <rb*@athop1.ath.vt.edu> 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?

Since you're doing cross product (ie. 3*3*3*3), manual loop of 4 level
deep would be the fastest in terms of algorithm. C vs. Python is
implementation detail.

In Bash shell, this is one-liner,
echo {a,b,c}{a,b,c}{a,b,c}{a,b,c}
or maybe two,
abc=(a b c)
echo {^abc}{^abc}{^abc}{^abc}

--
William Park <op**********@yahoo.ca>, Toronto, Canada
ThinFlash: Linux thin-client on USB key (flash) drive
http://home.eol.ca/~parkw/thinflash.html
BashDiff: Super Bash shell
http://freshmeat.net/projects/bashdiff/

[Erik Max Francis]

William Park wrote:

Since you're doing cross product (ie. 3*3*3*3), manual loop of 4 level
deep would be the fastest in terms of algorithm.

That's a Cartesian product, actually :-).

--
Erik Max Francis && ma*@alcyone.com && http://www.alcyone.com/max/
San Jose, CA, USA && 37 20 N 121 53 W && AIM erikmaxfrancis
All generalizations are dangerous, even this one.
-- Dumas Fils

[George Sakkis]

"rbt" <rb*@athop1.ath.vt.edu> wrote:

Thanks to all who were helpful... some of you guys are too harsh and
cynical. Here's what I came up with. I believe it's a proper
combination, but I'm sure someone will point out that I'm wrong ;)

groups =[list('abc'),list('abc'),list('abc'),list('abc')]

already = []

while 1:

LIST = []

for g in groups:
sample = random.sample(g, 1)
LIST.append(sample[0])

STRING = ''.join(LIST)
if STRING not in already:
print STRING
already.append(STRING)
if len(already) == 81:
break

UGH! I guess you're right, it's theoretically correct in the limit;
however IIRC, in your original post you were asking about the most
efficient way, not the least efficient, most obscure and inextensible
solution one could come up with. You're hoping to generate all
combinations AT RANDOM and you're wondering why some of us come out
"too harsh and cynical" ?! Try this with all letters instead of 'abc'
and when it ends get back to us, or rather our grand-grandchildren. In
the meantime, learn about recursion, generators and accumulating loops
and try to understand the right, efficient solutions already posted.

Cynically yrs,

George

PS: Btw, using ALL_CAPITALS (at least for local variables) is BAD
STYLE; the same holds for variables named 'list' and 'string',
independent of case.

[John Machin]

rbt wrote:

Thanks to all who were helpful... some of you guys are too harsh and
cynical.
Reality check: wander down to your nearest military establishment, ask a
drill sergeant to demonstrate "harsh and cynical".
Here's what I came up with. I believe it's a proper
combination, but I'm sure someone will point out that I'm wrong ;)

groups =[list('abc'),list('abc'),list('abc'),list('abc')]

already = []
In general, a set would be better than a list (1) conceptually (2) when
the number of elements is large.

while 1:

LIST = []
Read the style guide -- http://www.python.org/peps/pep-0008.html

for g in groups:
sample = random.sample(g, 1)
LIST.append(sample[0])

STRING = ''.join(LIST)
if STRING not in already:
print STRING
already.append(STRING)
if len(already) == 81:
break

You don't need to use random sampling. Paul Rubin has shown how it can
be done deterministically. The following is a generalisation of his
code; it generates all possible assemblies of size n from a list of
parts. Is this helpful?

def all_size_n_knickers(rqd_size, pieces):
npieces = len(pieces)
knicker_count = npieces ** rqd_size
austen = [npieces ** (rqd_size-k-1) for k in xrange(rqd_size)]
for i in xrange(knicker_count):
knicker = [pieces[j] for j in [(i // d) % npieces for d in austen]]
yield knicker

for alist in all_size_n_knickers(4, 'abc'):
print ''.join(alist)

print
print list(all_size_n_knickers(2, [1, 42, 666]))

[Bengt Richter]

On Thu, 14 Jul 2005 17:10:37 -0400, William Park <op**********@yahoo.ca> wrote:

rbt <rb*@athop1.ath.vt.edu> 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?

Since you're doing cross product (ie. 3*3*3*3), manual loop of 4 level
deep would be the fastest in terms of algorithm. C vs. Python is
implementation detail.

In Bash shell, this is one-liner,
echo {a,b,c}{a,b,c}{a,b,c}{a,b,c}
or maybe two,
abc=(a b c)
echo {^abc}{^abc}{^abc}{^abc}

It's a one liner in Python too ;-)

print ' '.join([x+y+z+q for s in ['abc'] for x in s for y in s for z in s for q in s])

aaaa aaab aaac aaba aabb aabc aaca aacb aacc abaa abab abac abba abbb abbc abca abcb abcc acaa a
cab acac acba acbb acbc acca accb accc baaa baab baac baba babb babc baca bacb bacc bbaa bbab bb
ac bbba bbbb bbbc bbca bbcb bbcc bcaa bcab bcac bcba bcbb bcbc bcca bccb bccc caaa caab caac cab
a cabb cabc caca cacb cacc cbaa cbab cbac cbba cbbb cbbc cbca cbcb cbcc ccaa ccab ccac ccba ccbb
ccbc ccca cccb cccc

Regards,
Bengt Richter

[Peter Hansen]

Bengt Richter wrote:

On Thu, 14 Jul 2005 17:10:37 -0400, William Park <op**********@yahoo.ca> wrote:
It's a one liner in Python too ;-)

>>> print ' '.join([x+y+z+q for s in ['abc'] for x in s for y in s for z in s for q in s])
Or for the cost of an import and a lambda, you can keep it looking real
obscure and generalize it to any size of sequence ('abcdef' or whatever)
and a result length of up to 52 elements:
from string import letters as L
cartesian = lambda seq, num: eval("list(%s for __ in [seq] %s)" % ('+'.join(L[:num]), 'for %s in __ ' * num % tuple(L[:num])))
# (there are spaces at any line breaks above)
cartesian('abcde', 6) ['aaaaaa', 'aaaaab', 'aaaaac', 'aaaaad', 'aaaaae', 'aaaaba',
....
'eeeeec', 'eeeeed', 'eeeeee'] len(_)

15625

<grin>

-Peter

[rbt]

Wow. That's neat. I'm going to use it. Thanks!

On Thu, 2005-07-14 at 19:52 -0400, Peter Hansen wrote:

Bengt Richter wrote:

On Thu, 14 Jul 2005 17:10:37 -0400, William Park <op**********@yahoo.ca> wrote:
It's a one liner in Python too ;-)

>>> print ' '.join([x+y+z+q for s in ['abc'] for x in s for y in s for z in s for q in s])
Or for the cost of an import and a lambda, you can keep it looking real
obscure and generalize it to any size of sequence ('abcdef' or whatever)
and a result length of up to 52 elements:
>>> from string import letters as L
>>> cartesian = lambda seq, num: eval("list(%s for __ in [seq] %s)" % ('+'.join(L[:num]), 'for %s in __ ' * num % tuple(L[:num])))
# (there are spaces at any line breaks above)
>>> cartesian('abcde', 6) ['aaaaaa', 'aaaaab', 'aaaaac', 'aaaaad', 'aaaaae', 'aaaaba',
...
'eeeeec', 'eeeeed', 'eeeeee'] >>> len(_)

15625

<grin>

-Peter

[Anton Vredegoor]

John Machin wrote:

You don't need to use random sampling. Paul Rubin has shown how it can
be done deterministically. The following is a generalisation of his
code; it generates all possible assemblies of size n from a list of
parts. Is this helpful?

def all_size_n_knickers(rqd_size, pieces):
npieces = len(pieces)
knicker_count = npieces ** rqd_size
austen = [npieces ** (rqd_size-k-1) for k in xrange(rqd_size)]
for i in xrange(knicker_count):
knicker = [pieces[j] for j in [(i // d) % npieces for d in austen]]
yield knicker

for alist in all_size_n_knickers(4, 'abc'):
print ''.join(alist)

print
print list(all_size_n_knickers(2, [1, 42, 666]))

Just testing out my ELCH JythonConsole :-)

def unint(i,symbols):
res = []
radix = len(symbols)
while i:
i,r = divmod(i,radix)
res.append(symbols[r])
return res[::-1]

start = int('10000',3)
finish = int('20000',3)
for i in range(start,finish):
print ''.join(unint(i,'abc')[1:])

This makes me wonder why we still don't have something like the unint
function above in the standard distribution.

Anton

[Steve Holden]

Anton Vredegoor wrote:

John Machin wrote:

You don't need to use random sampling. Paul Rubin has shown how it can
be done deterministically. The following is a generalisation of his
code; it generates all possible assemblies of size n from a list of
parts. Is this helpful?

def all_size_n_knickers(rqd_size, pieces):
npieces = len(pieces)
knicker_count = npieces ** rqd_size
austen = [npieces ** (rqd_size-k-1) for k in xrange(rqd_size)]
for i in xrange(knicker_count):
knicker = [pieces[j] for j in [(i // d) % npieces for d in austen]]
yield knicker

for alist in all_size_n_knickers(4, 'abc'):
print ''.join(alist)

print
print list(all_size_n_knickers(2, [1, 42, 666]))

Just testing out my ELCH JythonConsole :-)

def unint(i,symbols):
res = []
radix = len(symbols)
while i:
i,r = divmod(i,radix)
res.append(symbols[r])
return res[::-1]

start = int('10000',3)
finish = int('20000',3)
for i in range(start,finish):
print ''.join(unint(i,'abc')[1:])

This makes me wonder why we still don't have something like the unint
function above in the standard distribution.

Because it's not what you'd call (or, at least, it's not what I'd call)
universally required. As you have shown it is relatively easy to hack
something supp when it's needed, so since it isn't something that's
required by the majority it hasn't been added to the library.

regards
Steve
--
Steve Holden [phone] [phone]
Holden Web LLC http://www.holdenweb.com/

[Anton Vredegoor]

Steve Holden wrote:

This makes me wonder why we still don't have something like the unint
function above in the standard distribution.

Because it's not what you'd call (or, at least, it's not what I'd call)
universally required. As you have shown it is relatively easy to hack
something supp when it's needed, so since it isn't something that's
required by the majority it hasn't been added to the library.

How about the symmetry argument? One can use int for radix 1 to 32 (I
think) but for the reverse problem we only have hex or oct (and cannot
choose symbol lists but that's not so very important, if the whole
matter has any significance of course :-). Hey, unint might even win
the "more general" approval!

Anton

"or maybe it's just because it's difficult to find a good name for it"

[Steven D'Aprano]

On Thu, 28 Jul 2005 12:30:23 +0100, Steve Holden wrote:

This makes me wonder why we still don't have something like the unint
function above in the standard distribution.

Because it's not what you'd call (or, at least, it's not what I'd call)
universally required. As you have shown it is relatively easy to hack
something supp when it's needed, so since it isn't something that's
required by the majority it hasn't been added to the library.

Have you looked at what's in the standard Python library?

aifc.py => Stuff to parse AIFF-C and AIFF files.
imghdr.py => Recognize image file formats based on their first few bytes.
gopher.py => Gopher protocol client interface.
token.py => Token constants (from "token.h").

I'm sure they are useful to somebody, but do you really think that the
majority of Python users need to parse AIFF files?

Converting base-19 strings into integers is a rather niche need, but if
somebody bothered to write, document and provide unittests for such a
module, I'm sure it could be added to the standard library. It isn't as if
there is any policy of prohibiting specialist modules just because they
don't have universal need.

And no, I'm not volunteering. I may, if I get an itch, but at this moment
in my life I'm not that fussed one way or another.

--
Steven.

[Robert Kern]

Steven D'Aprano wrote:

Have you looked at what's in the standard Python library?

aifc.py => Stuff to parse AIFF-C and AIFF files.
imghdr.py => Recognize image file formats based on their first few bytes.
gopher.py => Gopher protocol client interface.
token.py => Token constants (from "token.h").

I'm sure they are useful to somebody, but do you really think that the
majority of Python users need to parse AIFF files?

There's a *huge* difference between, "Should we add such-and-such
module?" and "Should we keep such-and-such module?" The burden for the
latter is much, much lower.

Some of those modules are there because Python itself needs them
(token.py). Some are there because way back in the day before python-dev
got disciplined (or, for that matter, existed), a sufficient criterion
for inclusion into the standard library was, "Guido uses it." He needed
to parse AIFF files and various arcane image formats and do graphics
using the old SGI GL (the precursor to OpenGL). That's why some of that
stuff is there.

That said, I really would like a nice standard way to get the base-n
representations of numbers for at least 2 <= n <= 36.

--
Robert Kern
rk***@ucsd.edu

"In the fields of hell where the grass grows high
Are the graves of dreams allowed to die."
-- Richard Harter

[Steve Holden]

Steven D'Aprano wrote:

On Thu, 28 Jul 2005 12:30:23 +0100, Steve Holden wrote:

This makes me wonder why we still don't have something like the unint
function above in the standard distribution.

Because it's not what you'd call (or, at least, it's not what I'd call)
universally required. As you have shown it is relatively easy to hack
something supp when it's needed, so since it isn't something that's
required by the majority it hasn't been added to the library.

Have you looked at what's in the standard Python library?

aifc.py => Stuff to parse AIFF-C and AIFF files.
imghdr.py => Recognize image file formats based on their first few bytes.
gopher.py => Gopher protocol client interface.
token.py => Token constants (from "token.h").

I'm sure they are useful to somebody, but do you really think that the
majority of Python users need to parse AIFF files?

Converting base-19 strings into integers is a rather niche need, but if
somebody bothered to write, document and provide unittests for such a
module, I'm sure it could be added to the standard library. It isn't as if
there is any policy of prohibiting specialist modules just because they
don't have universal need.

And no, I'm not volunteering. I may, if I get an itch, but at this moment
in my life I'm not that fussed one way or another.

Well, here I have to fall back on history. I only started using Python
in the mid-to-late 1990's. In those days modules were added to the
language because they existed, and it was an easy way to distribute them.

Now Python has a significant user base the development of the language,
and the structure of the libraries, comes under more scrutiny, and there
is a general feeling that parsimony is to be preferred to bloat.

I can hardly disagree with you that aifc.py represents bloat by today's
standards, and I don't think I could name a single gopher user (though
that was certainly NOT the case in the mid-1990s).

and-i-still-can't-find-an-email-tool-with-dwim-ly y'rs - steve
--
Steve Holden [phone] [phone]
Holden Web LLC http://www.holdenweb.com/