給定一個數(shù)字n和一個除數(shù)列表A，我如何有效地找到乘以該數(shù)字時產(chǎn)生的所有除數(shù)組合？例如n = 12 A = [2, 3, 4]輸出：[[3, 2, 2], [2, 3, 2], [2, 2, 3], [4, 3], [3, 4]]這是我到目前為止所做的（代碼是我根據(jù) stackoverflow 上的許多查找質(zhì)因數(shù)分解問題之一重新改編的）：def products(n, A): if n == 1: yield [] for each_divisor in A: if n % each_divisor == 0: for new_product in products(n // each_divisor, A): yield new_product + [each_divisor]這段代碼似乎工作正常，但速度非常慢，如果我嘗試使用記憶化（A作為元組傳遞給函數(shù)以避免不可散列的類型錯誤），則代碼不會提供正確的結(jié)果。關(guān)于如何提高這段代碼的效率有什么建議嗎？我嘗試過的記憶代碼如下：class Memoize: def __init__(self, fun): self.fun = fun self.memo = {} def __call__(self, *args): if args not in self.memo: self.memo[args] = self.fun(*args) return self.memo[args]@Memoizedef products(n, A): [as above]當(dāng)使用上面定義的參數(shù)調(diào)用函數(shù)時n, A：>>> list(products(12, (2, 3, 4)))[[3, 2, 2]]如果沒有記憶，相同代碼的輸出是：[[3, 2, 2], [2, 3, 2], [2, 2, 3], [4, 3], [3, 4]]請注意，其他記憶功能（例如來自functools包@functools.lru_cache(maxsize=128)）會導(dǎo)致相同的問題。
1 回答
繁花如伊
TA貢獻(xiàn)2012條經(jīng)驗 獲得超12個贊
您可以將問題分解為遞歸部分以查找所有唯一組合，以及部分以查找每種排列的組合，而不是使用記憶。這應(yīng)該會大大減少你的搜索空間，并且只排列實際有效的選項。
要實現(xiàn)這一點，A應(yīng)該進(jìn)行排序。
第1部分：
對可用的可能分解圖進(jìn)行 DFS。通過僅選擇每個因子大于或等于其前一個因子的排序來截斷冗余分支的搜索。例如：
12
/ | \
/ | \
/ | \
2(x6) 3(x4) 4(x3)
/ | | \
2(x3) 3(x2) 3 4(x1)
/ |
2 3(x1)
粗體節(jié)點是導(dǎo)致成功分解的路徑。罷工節(jié)點是導(dǎo)致冗余分支的節(jié)點，因為n除以因子后剩余的節(jié)點小于因子。括號中未顯示剩余值的節(jié)點根本不會導(dǎo)致因式分解。對于低于當(dāng)前因子的因子，不會嘗試分支：當(dāng)我們嘗試 3 時，永遠(yuǎn)不會重新訪問 2，只有 3 和 4 等。
在代碼中：
A.sort()
def products(n, A):
def inner(n, A, L):
for i in range(len(A)):
factor = A[i]
if n % factor: continue
k = n // factor
if k < factor:
if k == 1:
yield L + [factor]
elif n in A:
yield L + [n]
break # Following k guaranteed to be even smaller
# until k == 1, which elif shortcuts
yield from inner(k, A[i:], L + [factor])
yield from inner(n, A, [])
這速度相當(dāng)快。在您的特定情況下，它僅檢查 4 個節(jié)點，而不是 ~30 個。事實上，您可以證明它檢查可能的絕對最小數(shù)量的節(jié)點。您可能獲得的唯一改進(jìn)是使用迭代而不是遞歸，我懷疑這會有多大幫助。
第2部分：
現(xiàn)在，您只需生成結(jié)果的每個元素的排列。Python 在標(biāo)準(zhǔn)庫中提供了直接執(zhí)行此操作的工具：
from itertools import chain, permutations
chain.from_iterable(map(permutations, products(n, A)))
您可以將其放入productsas的最后一行
yield from chain.from_iterable(map(permutations, inner(n, A, [])))
通過這種方式運行，list(products(12, A))我的機器性能提高了 20-30%（5.2μs 與 4.0μs）。運行一個更復(fù)雜的例子，比如list(products(2 * 3 * 4 * 5 * 5 * 7 * 11, [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 22]))顯示出更顯著的改進(jìn)：7 毫秒 vs 42 毫秒。
第 2b 部分：
您可以使用類似于此處所示的方法（無恥插件）過濾掉由于重復(fù)因素而發(fā)生的重復(fù)排列。適應(yīng)我們總是處理排序整數(shù)的初始列表的事實，它可以寫成這樣：
def perm_dedup(tup):
maximum = (-1,) * len(tup)
for perm in permutations(tup):
if perm <= maximum: continue
maximum = perm
yield perm
現(xiàn)在您可以在最后一行使用以下內(nèi)容：
yield from chain.from_iterable(map(perm_dedup, inner(n, A, [])))
時間仍然非常有利于這種完整的方法：問題的時間為 5.2μs 與 4.9μs，長示例的時間為 6.5ms 與 42ms。事實上，如果有的話，避免重復(fù)排列似乎可以進(jìn)一步減少時間。
長話短說
一種更高效的實現(xiàn)，僅使用標(biāo)準(zhǔn)庫并僅搜索唯一因式分解的唯一排列：
from itertools import chain, permutations
def perm_dedup(tup):
maximum = (-1,) * len(tup)
for perm in permutations(tup):
if perm <= maximum: continue
maximum = perm
yield perm
def products(n, A):
A = sorted(set(A))
def inner(n, A, L):
for i in range(len(A)):
factor = A[i]
if n % factor: continue
k = n // factor
if k < factor:
if k == 1:
yield L + [factor]
elif n in A:
yield L + [n]
break # Following k guaranteed to be even smaller
# until k == 1, which elif shortcuts
yield from inner(k, A[i:], L + [factor])
yield from chain.from_iterable(map(perm_dedup, inner(n, A, [])))
添加回答
舉報
0/150
提交
取消