P: n/a

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?  
Share this Question
P: n/a

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
precalculated 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, precalculation
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.  
P: n/a

On Thu, 20050714 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 precalculated 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, precalculation 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.  
P: n/a

On Wed, 20050713 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  
P: n/a

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.  
P: n/a

On Wed, 20050713 at 11:09 0400, rbt wrote: On Wed, 20050713 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 offlist that this is doing permutation, not
combination. Is there a way to make random.sample to do combinations?  
P: n/a

On Wed, 13 Jul 2005 11:09:25 0400, rbt wrote: On Wed, 20050713 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.  
P: n/a

rbt wrote: On Wed, 20050713 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  
P: n/a

rbt wrote: On Wed, 20050713 at 11:09 0400, rbt wrote:
On Wed, 20050713 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 offlist 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  
P: n/a

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.  
P: n/a

On Wed, Jul 13, 2005 at 05:07:33PM +0100, Duncan Smith wrote: rbt wrote: On Wed, 20050713 at 11:09 0400, rbt wrote:
On Wed, 20050713 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 offlist 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  
P: n/a

Jack Diederich wrote: On Wed, Jul 13, 2005 at 05:07:33PM +0100, Duncan Smith wrote:
rbt wrote:
On Wed, 20050713 at 11:09 0400, rbt wrote:
On Wed, 20050713 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 offlist 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  
P: n/a

"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(num1, seq):
for item in seq:
yield rest + [item]
else:
yield []
for comb in iterPermutations(4, list("abc")):
print ''.join(comb)
George  
P: n/a

"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  
P: n/a

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  
P: n/a

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")  
P: n/a

rbt wrote: On Wed, 20050713 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
Uhoh  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
merrygoround?  
P: n/a

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  
P: n/a

* Thomas Bartkus (20050713 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 "diehard"
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://groupsbeta.google.com/group/...192eda6?hl=en&  
P: n/a

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.  
P: n/a

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.)  
P: n/a

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, 20050714 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.)
 
P: n/a

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)]])  
P: n/a

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.  
P: n/a

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 oneliner,
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 thinclient on USB key (flash) drive http://home.eol.ca/~parkw/thinflash.html
BashDiff: Super Bash shell http://freshmeat.net/projects/bashdiff/  
P: n/a

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  
P: n/a

"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 grandgrandchildren. 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.  
P: n/a

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/pep0008.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_sizek1) 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]))  
P: n/a

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 oneliner, 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  
P: n/a

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  
P: n/a

Wow. That's neat. I'm going to use it. Thanks!
On Thu, 20050714 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  
P: n/a

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_sizek1) 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  
P: n/a

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_sizek1) 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 +44 150 684 7255 +1 800 494 3119
Holden Web LLC http://www.holdenweb.com/  
P: n/a

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"  
P: n/a

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 AIFFC 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 base19 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.  
P: n/a

Steven D'Aprano wrote: Have you looked at what's in the standard Python library?
aifc.py => Stuff to parse AIFFC 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 suchandsuch
module?" and "Should we keep suchandsuch 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 pythondev
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 basen
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  
P: n/a

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 AIFFC 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 base19 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 midtolate 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 mid1990s).
andistillcan'tfindanemailtoolwithdwimly y'rs  steve

Steve Holden +44 150 684 7255 +1 800 494 3119
Holden Web LLC http://www.holdenweb.com/   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 7840
 replies: 36
 date asked: Jul 21 '05
