Efficiently create generator to output lists of numbers in order

Question

I would like to create a generator that outputs a list of incrementing numbers. Ex.

[1]
[2]
..
[9]
[1,0]
[1,1]
[1,2]
..
[9,9]
[1,0,0]
[1,0,1]

I can do this in a brute force sort of way (not exactly right, but does not matter in this application, has leading 0s):

def generateNumbersStupid():
        for x1 in range(10):
                for x2 in range(10):
                        for x3 in range(10):
                                for x4 in range(10):
                                        for x5 in range(10):
                                                for x6 in range(10):
                                                        for x7 in range(10):
                                                                for x8 in range(10):
                                                                        yield [x1,x2,x3,x4,x5,x6, x7, x8]

Profile

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   56.083   56.083 part2_extended.py:1(<module>)
100000000   14.221    0.000   14.221    0.000 part2_extended.py:1(isGrowing)
     1278    0.001    0.000    0.004    0.000 part2_extended.py:17(meetsAdjacentCriteria)
100000000   13.181    0.000   27.452    0.000 part2_extended.py:25(isValid)
     1278    0.002    0.000    0.003    0.000 part2_extended.py:28(findAdjacents)
100000001    9.726    0.000   10.689    0.000 part2_extended.py:81(generateNumbersStupid)
    24310    0.031    0.000    0.046    0.000 part2_extended.py:9(inRange)
        1   17.942   17.942   56.083   56.083 part2_extended.py:92(calculateCount)
        1    0.000    0.000   56.083   56.083 part2_extended.py:99(main)
     6630    0.000    0.000    0.000    0.000 {len}
     9524    0.001    0.000    0.001    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
   194480    0.016    0.000    0.016    0.000 {pow}

But I would like to avoid the uglyiness and have something like this:

def generateNumbersArray(startNumber, endNumber):
        for num in range(startNumber, endNumber+1):
                number = []
                while True:
                        number.append(num%10)
                        num //=10
                        if num == 0:
                                break
                number.reverse()
                yield number

But this runs significantly slower.

Have also tried a cleaner:

def generateNumbersArray(startNumber, endNumber):
        for num in range(startNumber, endNumber+1):
                yield [int(x) for x in str(num)]

It is also significantly slower.

If I try to keep everything in place and not generating new arrays, it speeds it up quite a bit, but is still significantly slower.

def generateNumbersArrayInPlace(startNumber, endNumber):
        start = [int(x) for x in str(startNumber-1)]
        for num in range(startNumber, endNumber):
                lastIndex = len(start) - 1
                start[lastIndex] = start[lastIndex] + 1
                for digit in range(lastIndex, -1, -1):
                        if start[digit] > 9:
                                start[digit] = 0
                                if digit == 0:
                                        start.insert(0,1)
                                else:
                                        start[digit-1] = start[digit-1] + 1
                        else:
                                break
                yield start[:]

Profile

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   49.618   49.618 part2_extended.py:1(<module>)
 46191900    6.844    0.000    6.844    0.000 part2_extended.py:1(isGrowing)
     1278    0.001    0.000    0.004    0.000 part2_extended.py:17(meetsAdjacentCriteria)
 46191900    6.827    0.000   13.677    0.000 part2_extended.py:25(isValid)
     1278    0.002    0.000    0.003    0.000 part2_extended.py:28(findAdjacents)
 46191901   18.352    0.000   26.127    0.000 part2_extended.py:43(generateNumbersArray2)
     1278    0.002    0.000    0.003    0.000 part2_extended.py:9(inRange)
        1    9.814    9.814   49.618   49.618 part2_extended.py:92(calculateCount)
        1    0.000    0.000   49.618   49.618 part2_extended.py:99(main)
 46198530    1.865    0.000    1.865    0.000 {len}
     9524    0.001    0.000    0.001    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
    10224    0.001    0.000    0.001    0.000 {pow}

My question is if there is a pythonic way to do this efficiently?

Update:

@ggorlen something like

def generateNumbersItertools(startRange, endRange):
        gen = product([0,1,2,3,4,5,6,7,8,9], repeat=8)
        while True:
                cur = next(gen)
                yield [x for x in cur]

Profile:

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   90.430   90.430 part2_extended.py:1(<module>)
100000000   14.977    0.000   14.977    0.000 part2_extended.py:1(isGrowing)
        1    0.000    0.000   90.430   90.430 part2_extended.py:101(main)
     1278    0.001    0.000    0.004    0.000 part2_extended.py:17(meetsAdjacentCriteria)
100000000   14.289    0.000   29.317    0.000 part2_extended.py:25(isValid)
     1278    0.002    0.000    0.003    0.000 part2_extended.py:28(findAdjacents)
100000001   34.681    0.000   40.798    0.000 part2_extended.py:62(generateNumbersItertools)
    24310    0.032    0.000    0.048    0.000 part2_extended.py:9(inRange)
        1   20.315   20.315   90.430   90.430 part2_extended.py:94(calculateCount)
     6630    0.000    0.000    0.000    0.000 {len}
     9524    0.001    0.000    0.001    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
100000001    6.116    0.000    6.116    0.000 {next}
   194480    0.016    0.000    0.016    0.000 {pow}

Is also very slow.

Answer 1

Here is a recursive generator that gives sequences of a specified length with your requirement:

def f(length):
    if length == 1:
        for i in range(1,10):
            yield [i]
    else:
        for ls in (x for x in f(length-1)):
            for i in range(10):
                yield ls + [i]

So, you can invoke it with arbitrary length. [x for i in range(1,3) for x in f(i)] will result in:

[[1],
 [2],
 [3],
 [4],
 [5],
 [6],
 [7],
 [8],
 [9],
 [1, 0],
 [1, 1],
 [1, 2],
 [1, 3],
 [1, 4],
 ...

And if you are after a generator:

for item in (x for i in range(1, some_number) for x in f(i)):
    #do stuff

Answer 2

I ran some tests of my own comparing your "stupid" function generateNumbersStupid() to functions using itertools.product(), and just as the comments have been saying, it is faster.

For each of the following functions I ran 10 trials and took the average time (bear in mind, I iterated through all elements in the generator returned by the functions during the execution time):

stupid function

def generateNumbersStupid():
    for x1 in range(10):
            for x2 in range(10):
                    for x3 in range(10):
                            for x4 in range(10):
                                for x5 in range(10):
                                        for x6 in range(10):
                                            for x7 in range(10):
                                                for x8 in range(10):
                                                    yield [x1,x2,x3,x4,x5,x6,x7,x8]

Average Time: 16.5137999535 sec

itertools.product() generator

def generateNumbersItertools():
    return product(range(10), repeat=8)

Average Time: 3.82409999371 sec

It cleans up the code, as per your original desire, and it executes faster. Can't see the need for using a generator in this case, especially given how much faster returning and iterating through the list is.

Answer 3

Without running profiles, just using timeit I saw massive improvement by using itertools.product and by combining that with itertools.dropwhile you no longer have the preceding zeros in the leading lists although the first output will be an empty list this is the closest to what seems your desired output:

generateNumbers = (list(dropwhile((0).__eq__, p)) for p in product(range(10), repeat=8))

This results in:

[]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[1, 0]
[1, 1]
[1, 2]
[1, 3]
[1, 4]
[1, 5]
[1, 6]
[1, 7]
...