[Numpy-discussion] Is there a better way to do this?

Rick White rlw at stsci.edu
Wed Jul 21 22:03:03 CDT 2004


On Wed, 21 Jul 2004, Hee-Seng Kye wrote:

> I'm trying to write a program that computes six-digit numbers, in which
> the left digit is always smaller than its following digit (i.e., it's
> always ascending).

Here's another version that is a little faster still:

def f3():
  c = 1
  for p0 in range(0, 7):
    for p1 in range(p0+1, 8):
      for p2 in range(p1+1, 9):
        for p3 in range(p2+1, 10):
          for p4 in range(p3+1, 11):
            for p5 in range(p4+1, 12):
              print repr(c).rjust(3), "\t",
              print "%X %X %X %X %X %X" % (p0, p1, p2, p3, p4, p5)
              c += 1
  print "...Done"

This is plenty fast even for 9-digit numbers.  In fact it gets
a little faster for larger numbers of digits.

This problem is completely equivalent to the problem of finding
all combinations of 6 numbers chosen from the digits 0..11.
If you sort the digits of each combination in ascending order,
you get your numbers.  So if you search for something like
"Python permutations combinations" you can find other algorithms
that work.  Here's a recursive version:

def f4(n, digits=range(12)):
    if n==0:
        return [[]]
    rv = []
    for i in range(len(digits)):
        for cc in f4(n-1,digits[i+1:]):
            rv.append([digits[i]]+cc)
    return rv

That returns a list of all the number sets having n digits.
It's slower than the loop version but is more general.  There
are fast C versions of this sort of thing out there, I think.
				Rick White





More information about the Numpy-discussion mailing list