給定一個數字n和一個除數列表A，我如何有效地找到乘以該數字時產生的所有除數組合？例如n = 12 A = [2, 3, 4]輸出：[[3, 2, 2], [2, 3, 2], [2, 2, 3], [4, 3], [3, 4]]這是我到目前為止所做的（代碼是我根據 stackoverflow 上的許多查找質因數分解問題之一重新改編的）：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作為元組傳遞給函數以避免不可散列的類型錯誤），則代碼不會提供正確的結果。關于如何提高這段代碼的效率有什么建議嗎？我嘗試過的記憶代碼如下：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]當使用上面定義的參數調用函數時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)）會導致相同的問題。
1 回答
繁花如伊
TA貢獻2012條經驗 獲得超12個贊
您可以將問題分解為遞歸部分以查找所有唯一組合，以及部分以查找每種排列的組合，而不是使用記憶。這應該會大大減少你的搜索空間，并且只排列實際有效的選項。
要實現這一點，A應該進行排序。
第1部分：
對可用的可能分解圖進行 DFS。通過僅選擇每個因子大于或等于其前一個因子的排序來截斷冗余分支的搜索。例如：
12
/ | \
/ | \
/ | \
2(x6) 3(x4) 4(x3)
/ | | \
2(x3) 3(x2) 3 4(x1)
/ |
2 3(x1)
粗體節點是導致成功分解的路徑。罷工節點是導致冗余分支的節點，因為n除以因子后剩余的節點小于因子。括號中未顯示剩余值的節點根本不會導致因式分解。對于低于當前因子的因子，不會嘗試分支：當我們嘗試 3 時，永遠不會重新訪問 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, [])
這速度相當快。在您的特定情況下，它僅檢查 4 個節點，而不是 ~30 個。事實上，您可以證明它檢查可能的絕對最小數量的節點。您可能獲得的唯一改進是使用迭代而不是遞歸，我懷疑這會有多大幫助。
第2部分：
現在，您只需生成結果的每個元素的排列。Python 在標準庫中提供了直接執行此操作的工具：
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）。運行一個更復雜的例子，比如list(products(2 * 3 * 4 * 5 * 5 * 7 * 11, [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 22]))顯示出更顯著的改進：7 毫秒 vs 42 毫秒。
第 2b 部分：
您可以使用類似于此處所示的方法（無恥插件）過濾掉由于重復因素而發生的重復排列。適應我們總是處理排序整數的初始列表的事實，它可以寫成這樣：
def perm_dedup(tup):
maximum = (-1,) * len(tup)
for perm in permutations(tup):
if perm <= maximum: continue
maximum = perm
yield perm
現在您可以在最后一行使用以下內容：
yield from chain.from_iterable(map(perm_dedup, inner(n, A, [])))
時間仍然非常有利于這種完整的方法：問題的時間為 5.2μs 與 4.9μs，長示例的時間為 6.5ms 與 42ms。事實上，如果有的話，避免重復排列似乎可以進一步減少時間。
長話短說
一種更高效的實現，僅使用標準庫并僅搜索唯一因式分解的唯一排列：
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
提交
取消