Is there a better way to do this?
My question is not directly related to NumPy, but since many people here deal with numbers, I was wondering if I could get some help; it would be even better if there is a NumPy (or Numarray) function that takes care of what I want! I'm trying to write a program that computes sixdigit numbers, in which the left digit is always smaller than its following digit (i.e., it's always ascending). The best I could do was to have many embedded 'for' statement: c = 1 for p0 in range(0, 7): for p1 in range(1, 12): for p2 in range(2, 12): for p3 in range(3, 12): for p4 in range(4, 12): for p5 in range(5, 12): if p0 < p1 < p2 < p3 < p4 < p5: print repr(c).rjust(3), "\t", print "%X %X %X %X %X %X" % (p0, p1, p2, p3, p4, p5) c += 1 print "...Done" This works, except that it's very slow. I need to get it up to ninedigit numbers, in which case it's significantly slow. I was wondering if there is a more efficient way to do this. I would highly appreciate it if anyone could help. Many thanks. Kye
HeeSeng Kye wrote:
My question is not directly related to NumPy, but since many people here deal with numbers, I was wondering if I could get some help; it would be even better if there is a NumPy (or Numarray) function that takes care of what I want!
I'm trying to write a program that computes sixdigit numbers, in which the left digit is always smaller than its following digit (i.e., it's always ascending). The best I could do was to have many embedded 'for' statement:
c = 1 for p0 in range(0, 7): for p1 in range(1, 12): for p2 in range(2, 12): for p3 in range(3, 12): for p4 in range(4, 12): for p5 in range(5, 12): if p0 < p1 < p2 < p3 < p4 < p5: print repr(c).rjust(3), "\t", print "%X %X %X %X %X %X" % (p0, p1, p2, p3, p4, p5) c += 1 print "...Done"
This works, except that it's very slow. I need to get it up to ninedigit numbers, in which case it's significantly slow. I was wondering if there is a more efficient way to do this.
I would highly appreciate it if anyone could help.
This appears to give the same results and is significantly faster. def vers1(): c = 1 for p0 in range(0, 7): for p1 in range(p0+1, 12): for p2 in range(p1+1, 12): for p3 in range(p2+1, 12): for p4 in range(p3+1, 12): 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"
Many thanks.
Kye
 Jeff
On Wed, 21 Jul 2004, HeeSeng Kye wrote:
I'm trying to write a program that computes sixdigit 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 9digit 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(n1,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
Thanks a lot everyone for suggestions. On my slow machine (667 MHz), inefficient programs run even slower, and when I expand the program to calculate 9digit numbers, there is almost a 2minute difference! Thanks again. Best, Kye
HeeSeng Kye wrote:
My question is not directly related to NumPy, but since many people here deal with numbers, I was wondering if I could get some help; it would be even better if there is a NumPy (or Numarray) function that takes care of what I want!
I'm trying to write a program that computes sixdigit numbers, in which the left digit is always smaller than its following digit (i.e., it's always ascending). The best I could do was to have many embedded 'for' statement:
c = 1 for p0 in range(0, 7): for p1 in range(1, 12): for p2 in range(2, 12): for p3 in range(3, 12): for p4 in range(4, 12): for p5 in range(5, 12): if p0 < p1 < p2 < p3 < p4 < p5: print repr(c).rjust(3), "\t", print "%X %X %X %X %X %X" % (p0, p1, p2, p3, p4, p5) c += 1 print "...Done"
This works, except that it's very slow. I need to get it up to ninedigit numbers, in which case it's significantly slow. I was wondering if there is a more efficient way to do this.
I would highly appreciate it if anyone could help.
Sorry for taking a month. My solution is not faster than any of the ones that have already been proposed, but it is more elegant because it does not require the "n" nested for loops. Another hint is to use a generator for this purpose. Advantage is that the base and the number of digits can both be externally defined! Regards, Rob # As a reference, the general case where digits are not created in # order def gen(ndigits, base): dig = [0]*ndigits yield dig while 1: for num in range(ndigits1,1,1): if dig[num] < base  1: dig[num] += 1 break else: dig[num] = 0 else: return yield dig def genordered(ndigits, base): if ndigits > base: return dig = range(ndigits) yield dig while 1: for num in range(ndigits1,1,1): if dig[num] < basendigits+num: dig[num] += 1 for num2 in range(num+1,ndigits): dig[num2] = dig[num21] + 1 break else: return yield dig c = 1 for dig in genordered(ndigits = 6, base = 12): # This is the same as your print statement, but again independent of # the number of digits print "%3d\t"%c,' '.join(map(lambda x: "%X"%x, dig)) c += 1 print "...Done"
participants (4)

HeeSeng Kye

Jeffery D. Collins

Rick White

Rob Hooft