Calculating the nth result for itertools.product()

Question

I'm trying to calculate the nth result for itertools.product()

test = list(product('01', repeat=3))
print(test)

desired_output = test[0]
print(desired_output)

so instead of getting:

[('0', '0', '0'), ('0', '0', '1'), ('0', '1', '0'), ('0', '1', '1'), ('1', '0', '0'), ('1', '0', '1'), ('1', '1', '0'), ('1', '1', '1')]

I'm trying to get:

('0', '0', '0')

However as you probably already guessed, it doesn't scale well. Which is why I'm trying to only calculate the nth value.

I read through Nth Combination but I'm in need of the repeat functionality that product() offers

Thanks in advance!

Answer 1

The repeat functionality can be simulated quite easily. Here's a python version of the Ruby code described in this blog post.

def product_nth(lists, num):
    res = []
    for a in lists:
        res.insert(0, a[num % len(a)])
        num //= len(a)

    return ''.join(res)

Call this function as

>>> repeats = 50
>>> chars = '01'
>>> product_nth([chars] * repeats, 12345673)
'00000000000000000000000000101111000110000101001001'

---

Here's some timeit tests:

repeat = 50
idx = 112345673

%timeit i = product_nth(['01'] * repeat, idx)
%%timeit
test = product('01', repeat=repeat)
one = islice(test, idx, idx+1)
j = ''.join(next(one))

2.01 s ± 22.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
36.5 µs ± 201 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

print(i == j)
True

---

The other answer is misleading because it misrepresents the functionality of islice. As an example, see:

def mygen(r):
    i = 0
    while i < r:
        print("Currently at", i)
        yield i
        i += 1

list(islice(mygen(1000), 10, 11))

# Currently at 0
# Currently at 1
# Currently at 2
# Currently at 3
# Currently at 4
# Currently at 5
# Currently at 6
# Currently at 7
# Currently at 8
# Currently at 9
# Currently at 10
# Out[1203]: [10]

islice will step through every single iteration, discarding results until the index specified. The same thing happens when slicing the output of product—the solution is inefficient for large N.

Answer 2

If you build out the whole list if, of course, won't scale well because calling list() runs through the whole iterator.

If you only need the first value you can just use next(test) to pull off the first value of the iterator. This doesn't require building the whole list and will be very fast.

You can use also itertools.islice() to get a specific part of the iterator without building out the whole list and it's quite fast. But understand that it will still iterate up to the the Nth value. This is a very pythonic way to do this, it's memory-efficient, and easy to read. Whether this is fast enough depends on how large your N needs to be. For example this produces a value of the 200000th combination quite quickly for me:

from itertools import product, islice

test = product('01', repeat=20)
one = islice(test, 200000, 200001)
print(''.join(next(one)))

# 00110000110101000000