合并图像的最有效算法？

Question

我正在寻找解决我面临的挑战的最佳算法：我有一个 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

我还应该说元素是图像，我使用 Pillow 库中的 Image.alpha_composite(img1, img2) 将它们组合在一起。所以我必须创建临时图像，它是两个图像组合的结果，然后我必须将它与下一个图像组合，再次创建临时结果，然后再次将临时图像与下一个图像组合，依此类推。

我正在寻找使用 Python 获得组合的最有效方法。提前谢谢你

Answer 1

我不知道是否有任何方法可以优化图像的组合，但抛开这一点，这只是一个组合问题案例，您可以使用一些非常标准的方法（包括回溯）来解决。

根据我掌握的信息，我会选择回溯，因为它可能会为您节省一些 space 和中间结果的冗余计算。

下面是一些示例代码：

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']和['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

Space 复杂度：递归栈的深度为n，外层列表的长度，部分结果也不会越过n个元素，但是最终的结果是 m^n 因为这是可能组合的数量。如果您将结果列表视为辅助 space，则 space 复杂度为 m^n。如果不是，那就是 n.

Answer 2

这是使用生成器的好地方。这是一种方法。它与任何可能的方法一样有效。其他几个也是可能的，例如可以修改 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

对于space，这仅使用长度为 N 的索引数组，其中 N 是输入列表的数量。每个生成列表的摊销时间为 O(1) 以增加索引。当然你还需要 O(N) 来构建每个输出列表。

这个解决方案很好，因为您永远不需要存储所有组合。它们很容易变得很大。

合并图像的最有效算法？

Most efficient Algorithm for merging images?

python

algorithm

recursion

combinations

python-imaging-library