Is there a better way to do this?
![](https://secure.gravatar.com/avatar/b421e599fbe55a7503378c21ecd9a7ff.jpg?s=120&d=mm&r=g)
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 six-digit 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 nine-digit 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
![](https://secure.gravatar.com/avatar/995bd9e442ad6095ddbbb27d1c209c43.jpg?s=120&d=mm&r=g)
Hee-Seng Kye wrote:
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
![](https://secure.gravatar.com/avatar/c3fbc70c6e7101b4905799649b5572e7.jpg?s=120&d=mm&r=g)
On Wed, 21 Jul 2004, Hee-Seng Kye wrote:
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
![](https://secure.gravatar.com/avatar/b421e599fbe55a7503378c21ecd9a7ff.jpg?s=120&d=mm&r=g)
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 9-digit numbers, there is almost a 2-minute difference! Thanks again. Best, Kye
![](https://secure.gravatar.com/avatar/802b07155a8ab3996b825eca778f770e.jpg?s=120&d=mm&r=g)
Hee-Seng Kye wrote:
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(ndigits-1,-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(ndigits-1,-1,-1): if dig[num] < base-ndigits+num: dig[num] += 1 for num2 in range(num+1,ndigits): dig[num2] = dig[num2-1] + 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"
![](https://secure.gravatar.com/avatar/995bd9e442ad6095ddbbb27d1c209c43.jpg?s=120&d=mm&r=g)
Hee-Seng Kye wrote:
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
![](https://secure.gravatar.com/avatar/c3fbc70c6e7101b4905799649b5572e7.jpg?s=120&d=mm&r=g)
On Wed, 21 Jul 2004, Hee-Seng Kye wrote:
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
![](https://secure.gravatar.com/avatar/b421e599fbe55a7503378c21ecd9a7ff.jpg?s=120&d=mm&r=g)
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 9-digit numbers, there is almost a 2-minute difference! Thanks again. Best, Kye
![](https://secure.gravatar.com/avatar/802b07155a8ab3996b825eca778f770e.jpg?s=120&d=mm&r=g)
Hee-Seng Kye wrote:
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(ndigits-1,-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(ndigits-1,-1,-1): if dig[num] < base-ndigits+num: dig[num] += 1 for num2 in range(num+1,ndigits): dig[num2] = dig[num2-1] + 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)
-
Hee-Seng Kye
-
Jeffery D. Collins
-
Rick White
-
Rob Hooft