Python - 将所有可能的 5 种组合编码为整数

Question

我有一组 25 个整数，范围从 0 到 24，我的应用程序涉及选择其中 5 个（没有重复值，没有值可以选择多次），获得像这样的组合 [ 15, 7, 12、3、22]。重要的是要考虑到前面的组合被认为等于[7, 22, 12, 15, 3]，顺序并不重要，只有值才重要。

通过应用二项式系数（25 选 5），我们可以发现有 53.130 种可能的组合。我想将所有可能的组合编码为一个整数，以便从 0 到 53129 的所有值都链接到一个组合。

Answer 1

使用more_itertools.nth_combination它可以计算第 n 个组合，而无需计算所有先前的组合：

# pip install more-itertools
from more_itertools import nth_combination

nth_combination(range(25), 5, 0)
# (0, 1, 2, 3, 4)

nth_combination(range(25), 5, 42)
# (0, 1, 2, 5, 7)

nth_combination(range(25), 5, 53129)
# (20, 21, 22, 23, 24)

您可以通过将上面的内容与functools.partial/结合起来使事情变得更有趣cache：

from functools import partial, cache

encode = partial(nth_combination, range(25), 5)
# or with a cache
# encode = cache(partial(nth_combination, range(25), 5))

encode(0)
# (0, 1, 2, 3, 4)

encode(42)
# (0, 1, 2, 5, 7)

encode(53129)
# (20, 21, 22, 23, 24)

效率

优点nth_combination是对于大范围，不需要计算所有n-1个组合来访问第n个。此外，不需要存储所有组合，从而提高 CPU 和内存效率。与cache此相结合，可以在内存和 CPU 之间做出折衷，避免在多次请求相同的代码时重新计算相同的值两次。

但是，如果您最终必须访问所有值，那么预先计算@ti7所示的所有组合将更加简单和高效，但需要从一开始就计算和存储所有值：

from itertools import combinations

encode = list(combinations(range(25), 5))

encode[0]
# (0, 1, 2, 3, 4)

encode[42]
# (0, 1, 2, 5, 7)

encode[53129]
# (20, 21, 22, 23, 24)