Most efficient Algorithm for merging images?-CodePudding

I am looking for the best algorithm to solve the challange I faced: I have a list of K lists where each list contains N elements(every list can contain different number of elements, except 0) and I want to get all combinations of each element from each list(starting from first one) with each element from following lists, so the combination must have K-number elements and the each element inside the each combination must be in the same place as the Nth-number of the list where this element came from.

list of K lists where each list contains N elements:

[ [a1, b1, ..., N],
  [a2, b2, ..., N],
          ....,
  [aK, bK, ..., N]]

For example, for the list:

[[a1, b1],
 [a2],
 [a3, b3, c3]]

Combinations are

a1a2a3
a1a2b3
a1a2c3
b1a2a3
b1a2b3
b1a2c3

I should also say that the elements are images, and I combine them using Image.alpha_composite(img1, img2) from Pillow library. So I have to create temp image that is a result of combination of two images and then I have tocombine it with the next image, creating again temp result and then again combine the temp with next image and so on.

I am looking for the most efficient way to do get the combination using Python. Thank you in advance

CodePudding user response：

I don't know if there is any methods to optimize the combination of images but putting that aside, this is just a combination problem case that you can solve with some pretty standard methods including backtracking.

With the information I have I would go with backtracking, since it probably saves you some space and redundant computation of intermediate results.

Here's some example code:

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

The good thing about this method is that if you do some computationally intensive calculations along the way, you can reuse them.

For example: ['a1', 'a2', 'a3'] and ['a1', 'a2', 'b3'] are both among the results and they have a prefix in common. When you come up the recursive tree after you have added the first to the results, you already have ['a1', 'a2'] from the previous calculation (assuming it's computationally expensive), you can reuse them and just combine b3 with them.

Time complexity: If we consider the combination part of images (like in this simplified example where it's just adding the elements to a list) a constant operation, then you are doing length of list 0 * length of list 1 *.... length of list n-1 operations where n is the length of the outer list where the individual lists of images resides. If we consider m to be the length of the longest list, this becomes m0 * m1 * ... * m(n-1) = m^n

Space complexity: The depth of the recursive stack is n, the length of the outer list, the partial results also never go over n elements, but the final results are m^n as this is the number of possible combinations. If you consider the results list as auxiliary space then space complexity is m^n. If not, it's just n.

CodePudding user response：

This is a nice place to use a generator. Here's one way. Several others are possible, for example user1984's could be modified.

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))

Running this matches your example:

$ python gen.py
a1a2a3
a1a2b3
a1a2c3
b1a2a3
b1a2b3
b1a2c3

For space this uses only the length N index array where N is the number of input lists. Amortized time per generated list is O(1) to increment the indices. Of course you also need O(N) to build each output list.

This solution is nice because you never need to store all the combinations. They can easily get very big.