yet another noob question

[Alex Martelli]

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