我有三個地方，每個地方都可以從 set 中取一個值{1, 2, 3}。我正在使用以下 python 腳本來生成所有可能的產品：
import itertools
options = [1, 2, 3]
for element in itertools.product(options, options, options):
print(element)
輸出：
(1, 1, 1)
(1, 1, 2)
(1, 1, 3)
(1, 2, 1)
(1, 2, 2)
(1, 2, 3)
(1, 3, 1)
(1, 3, 2)
(1, 3, 3)
(2, 1, 1)
(2, 1, 2)
(2, 1, 3)
(2, 2, 1)
(2, 2, 2)
(2, 2, 3)
(2, 3, 1)
(2, 3, 2)
(2, 3, 3)
(3, 1, 1)
(3, 1, 2)
(3, 1, 3)
(3, 2, 1)
(3, 2, 2)
(3, 2, 3)
(3, 3, 1)
(3, 3, 2)
(3, 3, 3)
但是，在我的用例中，我想消除其中的一些產品。例如，
- 如果我認為
(1, 1, 1)是一個輸出，那么我們可以消除(2, 2, 2)和(3, 3, 3)。由于兩者具有相同的配置：所有地方都有相同的 number。 - 如果我認為
(1, 1, 2)是一個輸出，那么我們可以消除(2, 2, 3),(2, 2, 1),(1, 2, 1),(3, 1, 3)。由于它們都具有以下配置：兩個地方應該有相同的數字。
uj5u.com熱心網友回復：
您正在尋找的是數字的磁區，映射到集合的元素。
在您的情況下，我們需要 3 個元素，因此N=3. 然后我們找到所有可以將正整數相加等于三的方法，并允許第th 個整數表示當前集合中第 th 個元素的i計數。i
在這種情況下，我將使用David Eppstein的Python Algorithms and Data Structures中的磁區生成代碼：
def revlex_partitions(n):
"""
Integer partitions of n, in reverse lexicographic order.
The output and asymptotic runtime are the same as mckay(n),
but the algorithm is different: it involves no division,
and is simpler than mckay, but uses O(n) extra space for
a recursive call stack.
"""
if n == 0:
yield []
if n <= 0:
return
for p in revlex_partitions(n-1):
if len(p) == 1 or (len(p) > 1 and p[-1] < p[-2]):
p[-1] = 1
yield p
p[-1] -= 1
p.append(1)
yield p
p.pop()
有了這個，我們現在只需要遍歷這些磁區，并映射值：
def configurations(elements, count):
for partition in revlex_partitions(count):
if len(partition) <= len(elements):
yield tuple(x for x, c in zip(elements, partition) for _ in range(c))
例子：
>>> print(list(configurations({14, 23, 55, 78}, 4)))
[(14, 14, 14, 14), (14, 14, 14, 23), (14, 14, 23, 23), (14, 14, 23, 78), (14, 23, 78, 55)]
>>> print(list(configurations({1, 2, 3}, 4)))
[(1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 2, 2), (1, 1, 2, 3)]
性能說明：
漸近地說，這有一個數字的指數磁區數，所以運行時間當然是指數的。我嘗試了對上述磁區演算法的一些自己的修改（修剪不預先滿足大小要求的元素），但只能實作大約 4 倍的加速，這是相當大的輸入需要幾秒鐘或更長時間.
在上面的鏈接中還有一個磁區函式的迭代實作，但它也更復雜 - 如果性能是一個問題，請考慮嘗試那個。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/486803.html
下一篇：使用數學在網格內查找專案的位置