如何在一定条件下组合大列表

Question

我试图解决一个来自生物学领域的问题，在这个问题中，我必须把每个大元素的局部次优解结合起来，这样每个子粒子都是唯一的。问题是，这些可能性可以扩展到+4000个局部次优解，而元素的可能性可以扩展到+30000个局部次优解。笛卡尔积不是一个选项，因为组合列表是一个n*m*p*。。。问题，没有一个超越itertools的算法是不可能的。你知道吗

一般模式为：

[
  [ [a,b,c],[d,e,a],[f], ...],
  [ [f,e,t],[a,b,t],[q], ...],
  [ [a,e,f],[],[p], ... up to 4.000],
  ... up to 30.000
]

[ [a,b,c],[d,e,a],[f],.....],->；元素的次优解群。#1个

我想尽快找到

• 首先：一个解决方案，这意味着每个元素的一个次优解决方案的组合（可以包括空白列表），这样就没有重复。例如[[a，b，c]，[f，e，t][p]]。

• 第二个：所有兼容的解决方案。

我知道这是一个开放的问题，但我需要一些指导或一般算法来面对这个问题，我可以进一步调查，如果我有什么开始。你知道吗

我在剩下的实验室工作中使用python，但是我对其他语言持开放态度。你知道吗

我们可以从一个基本的解算器开始，这个解算器在总次优和列表数量方面处理的可能性较小。你知道吗

最好的。你知道吗

编辑1

一个非常简短的实例：

[[[1,2,3][1,2,4],[1,2,5],[5,8]],
[[1,3][7,8],[6,1]],
[[]],
[[9,10][7,5],[6,9],[6,10]]]

最优解（来自第#行）：

#1 [1,2,3]
#2 [7,8]
#3 [9,10]

Output: [[1,2,3],[7,8],[9,10]]

在这里可以看到https://pastebin.com/qq4k2FdW

Answer 1

这里有几个算法。您可以使用itertools对所有可能的组合进行暴力搜索，非常简单：

from itertools import product, chain

def get_compatible_solutions(subsolutions):
    for sol in product(*subsolutions):
        if len(set(chain.from_iterable(sol))) == sum(map(len, sol)):
            yield sol

# Test
example = [
    [[1, 2, 3], [1, 2, 4], [1, 2, 5], [5, 8]],
    [[1, 3], [7, 8], [6, 1]],
    [[]],
    [[9, 10], [7, 5], [6, 9], [6, 10]]
]

# Get one solution
print(next(get_compatible_solutions(example)))
# ([1, 2, 3], [7, 8], [], [9, 10])

# Get all solutions
print(*get_compatible_solutions(example), sep='\n')
# ([1, 2, 3], [7, 8], [], [9, 10])
# ([1, 2, 3], [7, 8], [], [6, 9])
# ([1, 2, 3], [7, 8], [], [6, 10])
# ([1, 2, 4], [7, 8], [], [9, 10])
# ([1, 2, 4], [7, 8], [], [6, 9])
# ([1, 2, 4], [7, 8], [], [6, 10])
# ([1, 2, 5], [7, 8], [], [9, 10])
# ([1, 2, 5], [7, 8], [], [6, 9])
# ([1, 2, 5], [7, 8], [], [6, 10])
# ([5, 8], [1, 3], [], [9, 10])
# ([5, 8], [1, 3], [], [6, 9])
# ([5, 8], [1, 3], [], [6, 10])
# ([5, 8], [6, 1], [], [9, 10])

另一种可能是一次递归搜索一行。这将比笛卡尔积探索更少的候选解，因为一旦次优解被排除在搜索路径之外，就不会处理包括它在内的任何组合。你知道吗

def get_compatible_solutions(subsolutions):
    current = [None] * len(subsolutions)
    seen = set()
    yield from _get_compatible_solutions_rec(subsolutions, current, 0, seen)

def _get_compatible_solutions_rec(subsolutions, current, i, seen):
    if i >= len(subsolutions):
        yield tuple(current)
    else:
        for subsol in subsolutions[i]:
            if any(s in seen for s in subsol):
                continue
            seen.update(subsol)
            current[i] = subsol
            yield from _get_compatible_solutions_rec(subsolutions, current, i + 1, seen)
            seen.difference_update(subsol)