计算itertools.product()的第n个结果

Question

我正在尝试计算itertools.product()函数的第n个结果。

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

desired_output = test[0]
print(desired_output)

所以不要得到：

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

我想要实现以下目标：

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

然而，正如您可能已经猜到的那样，它并不很好地扩展。这就是为什么我正在尝试仅计算第n个值。

我阅读了Nth Combination，但我需要product()提供的重复功能

提前感谢！

- Jacob W. Dallas

Answer 1

可以很容易地模拟repeat功能。这是一个Python版本的Ruby代码，描述在这篇博客文章中。

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

    return ''.join(res)

将此函数调用为

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

---

以下是一些 timeit 测试：

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

另一个答案是误导性的，因为它歪曲了islice的功能。例如，请参见：

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]

< p > islice会遍历每个迭代结果，直到指定的索引位置。当对product的输出进行切片时，也会发生同样的事情——对于较大的N，这种解决方案效率低下。

- cs95

Answer 2

如果你构建整个列表，当然不会很好地扩展，因为调用list()会遍历整个迭代器。

如果你只需要第一个值，可以使用next(test)来提取迭代器的第一个值。这不需要构建整个列表，速度非常快。

你也可以使用itertools.islice()获取迭代器的特定部分，而不必构建整个列表，这非常快速。但要理解它仍然会迭代到第N个值。这是一种非常Pythonic的方法，它具有内存效率和易读性。是否足够快取决于你需要的N的大小。例如，对我来说，这很快地产生了第200000个组合的值：

from itertools import product, islice

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

# 00110000110101000000

- Mark

---

@JacobW.Dallas 这个答案是误导性的。组合确实不会立即生成。islice 会生成并且丢弃到指定索引之前的所有内容。请参见我的答案中的一些 timeit 测试。 - cs95

@coldspeed 除了一些夸张之外，这是一个很好的、非常符合Python风格的解决方案，直到组合数量变得如此之大以至于它不再适用。它绝对不应该被点踩。 - Mark

解决方案本质上并没有错，只是使用了误导性的语言。dv 就是为此而设的。 - cs95