我正在尋找解決我面臨的挑戰的最佳演算法：我有一個 K 串列的串列，其中每個串列包含 N 個元素（每個串列可以包含不同數量的元素，除了 0），我想獲得每個元素的所有組合來自每個串列（從第一個開始）以及來自以下串列的每個元素，因此組合必須具有 K 個元素，并且每個組合中的每個元素必須與該元素所在的串列的第 N 個元素位于同一位置來自。
K 個串列的串列，其中每個串列包含 N 個元素：
[ [a1, b1, ..., N],
[a2, b2, ..., N],
....,
[aK, bK, ..., N]]
例如，對于串列：
[[a1, b1],
[a2],
[a3, b3, c3]]
組合是
a1a2a3
a1a2b3
a1a2c3
b1a2a3
b1a2b3
b1a2c3
我還應該說元素是影像，我使用Image.alpha_composite(img1, img2)Pillow 庫將它們組合起來。所以我必須創建臨時影像，它是兩個影像組合的結果，然后我必須將它與下一個影像組合，再次創建臨時結果，然后再次將臨時影像與下一個影像組合，依此類推。
我正在尋找使用 Python 進行組合的最有效方法。先感謝您
uj5u.com熱心網友回復：
我不知道是否有任何方法可以優化影像組合，但暫且不提，這只是一個組合問題案例，您可以使用一些非常標準的方法（包括回溯）來解決。
根據我掌握的資訊，我會進行回溯，因為它可能會為您節省一些空間和中間結果的冗余計算。
下面是一些示例代碼：
def backtrack(idx, images, partial_results, results):
if idx >= len(images):
results.append(partial_results[:])
return
for image in images[idx]:
partial_results.append(image)
backtrack(idx 1, images, partial_results, results)
partial_results.pop()
images = [["a1", "b1"],["a2"], ["a3", "b3", "c3"]]
results = []
backtrack(0, images, [], results)
print(results)
## outputs
## [['a1', 'a2', 'a3'], ['a1', 'a2', 'b3'], ['a1', 'a2', 'c3'], ['b1', 'a2', 'a3'], ['b1', 'a2', 'b3'], ['b1', 'a2', 'c3']]
這種方法的好處是，如果您在此程序中進行了一些計算密集型計算，則可以重復使用它們。
例如：['a1', 'a2', 'a3']and['a1', 'a2', 'b3']都在結果中并且它們有一個共同的前綴。當您在將第一個結果添加到結果后出現遞回樹時，您已經['a1', 'a2']從先前的計算中獲得了（假設它的計算成本很高），您可以重用它們并b3與它們組合。
時間復雜度：如果我們考慮影像的組合部分（就像在這個簡單的例子中，它只是將元素添加到串列中）一個常量操作，那么你正在做的length of list 0 * length of list 1 *.... length of list n-1操作是其中 n 是外部串列的長度，其中單個串列的長度影像駐留。如果我們考慮m是最長串列的長度，這變成m0 * m1 * ... * m(n-1) = m^n
空間復雜度：遞回堆疊的深度為 ，外鏈n的長度，部分結果也不會遍歷n元素，但最終結果是m^n因為這是可能的組合數。如果您將結果串列視為輔助空間，則空間復雜度為m^n. 如果沒有，那只是n.
uj5u.com熱心網友回復：
這是使用生成器的好地方。這是一種方法。其他幾個是可能的，例如可以修改 user1984。
def combinations(lists):
indices = [0] * len(lists)
while True:
yield [lists[i][j] for i, j in enumerate(indices)]
for k in reversed(range(len(lists))):
if indices[k] < len(lists[k]) - 1:
indices[k] = 1
break
indices[k] = 0
else:
return
data = [['a1', 'b1'],
['a2'],
['a3', 'b3', 'c3']]
for comb in combinations(data):
print(''.join(comb))
運行此匹配您的示例：
$ python gen.py
a1a2a3
a1a2b3
a1a2c3
b1a2a3
b1a2b3
b1a2c3
對于空間，這僅使用長度為 N 的索引陣列，其中 N 是輸入串列的數量。每個生成的串列的攤銷時間是 O(1) 以增加索引。當然，您還需要 O(N) 來構建每個輸出串列。
這個解決方案很好，因為你永遠不需要存盤所有的組合。它們很容易變得非常大。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/391946.html
上一篇：存在給定起點的完全自回避步行
下一篇：將vector<vector<string>>轉換為vector<vector<double>>的最佳方法是什么？