yet another noob question
Alex Martelli
aleax at mac.com
Sun Aug 13 15:30:41 EDT 2006
mike_wilson1333 <mwilson1333 at hotmail.com> wrote:
> I would like to generate every unique combination of numbers 1-5 in a 5
> digit number and follow each combo with a newline. So i'm looking at
> generating combinations such as: (12345) , (12235), (55554) and so on.
> What would be the best way to do this? So, basically i'm looking for a
> list of all combinations of 1-5 in a 5 digit unique number. Also, when
> I send the list to print there can't be any duplicates of the combos.
[[warning: haven't tried out any of the following code, just typed it
into the newsreader, so there may be typos or whatnot, but, I'm focusing
on communicating the general ideas anyway:-)]]
A working but boilerplatey solution is to nest 5 loops...:
r = range(1, 6)
for i0 in r:
for i1 in r:
for i2 in r:
for i3 in r:
for i4 in r:
print '(%d%d%d%d%d)' % (i0,i1,i2,i3,i4)
While this does work, it's inelegant -- "flat is better than nested",
and all that. Hard-coding the exact number of nested loops, etc, is
definitely not ideal.
So here's an alternative:
def allcomb(seq=range(1, 6), reps=5):
counter = reps*[0]
format = '(' + '%s'*reps + ')'
maxcount = len(seq)-1
while True:
print format % tuple(seq[i] for i in counter)
i = 0
while i<reps and counter[i]==maxcount:
counter[i] = 0
i += 1
if i >= reps: return
counter[i] += 1
You can have many variations on this theme, but basically what they're
doing is "counting in base N" (where N is len(seq)) -- variations around
that are mere stylistic issues. For example, the inner loop (after the
print statement) could become:
for i in range(reps):
if counter[i] < maxcount:
counter[i] += 1
break
else:
counter[i] = 0
else:
return
or, you could loop with "for i, c in enumerate(counter):", etc, etc --
but these variations are all implementing the same algorithm. One
algorithms that's definitely different enough to distinguish is to use
recursion -- but it won't offer much advantage over this one.
Alex
More information about the Python-list
mailing list