all possible combinations

[John Machin]

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

 

[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

 

[Paul Rubin]

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]

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]

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 <[email protected]>, 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]

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 .

 

[George Sakkis]

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]

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]

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]

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)
['aaaaaa', 'aaaaab', 'aaaaac', 'aaaaad', 'aaaaae', 'aaaaba',
....
'eeeeec', 'eeeeed', 'eeeeee']15625

<grin>

-Peter

 

[rbt]

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

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)
['aaaaaa', 'aaaaab', 'aaaaac', 'aaaaad', 'aaaaae', 'aaaaba',
...
'eeeeec', 'eeeeed', 'eeeeee']15625

<grin>

-Peter

 

[Anton Vredegoor]

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]

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

 

[Anton Vredegoor]

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]

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.

 

[Robert Kern]

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
(e-mail address removed)

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

 

[Steve Holden]

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