python - 基于可能的对创建组合

Question

我有 n导致 n(n-1)/2 的索引成对组合，例如为 n=3(i,j,k) -> (i,j), (i,k), (j,k)现在对于这些对中的每一个，我都知道可能性，例如

(i,j) = (1,2), (1,3), (2,2)
(i,k) = (2,2), (1,2), (2,4)
(j,k) = (1,2), (4,3), (2,2)

换句话说，在某些组合中 (i,j,k)我们必须有那个 (i,j)是 (1,2)或 (1,3)或 (2,2)其他对也一样。我希望构建所有可能的组合，因此在上面的示例中只有两种可能的组合:

(i,j,k) = (2,2,2)
(i,j,k) = (1,2,2)

我目前已按如下方式实现此程序:

import numpy as np

ij = np.array(([1,2], [1,3], [2,2]))
ik = np.array(([2,2], [1,2], [2,4]))
jk = np.array(([1,2], [4,3], [2,2]))

possibilities = []

possible_i = np.union1d(ij[:,0], ik[:,0])
possible_j = np.union1d(ij[:,1], jk[:,0])
possible_k = np.union1d(ik[:,1], jk[:,1])

for i in possible_i:
    for j in possible_j:

        if ([i,j] == ij).all(1).any():     
            for k in possible_k:
                if (([i,k] == ik).all(1).any() and
                    ([j,k] == jk).all(1).any()):
                    print(i,j,k)

尽管这有效并且可以轻松适应任何 n ，它对我来说似乎不是很有效，因为它例如检查组合:

1 2 2
1 2 2
1 2 3
1 2 4
1 3 2
1 3 3
1 3 4
2 2 2
2 2 2
2 2 3
2 2 4

当然，我们检查后知道 (i,j,k) = (i,2,3)无效，我们不必重新检查此表单的其他组合。有没有更有效的方法来解决这个任务(这也适用于更高的 n )？

Answer 1

我们用长度列表表示可能的组合 n .我们还没有得到任何信息的索引将包含 None .
每轮将处理一对索引，并检查该对的所有规则。
如果该对的第一个值存在于前一回合的可能组合中，而第二个值从未被触及(None 也是如此)，我们将其添加为本回合的新可能组合。
如果两个值都存在于先前的组合中，则确认它可能有效，我们也将其添加。
我们可以放弃上一回合的结果，因为我们之前认为可能但在本回合尚未验证的组合是不可能的。
所以，代码:

from itertools import combinations

def possible_combs(n, pairs_list):
    # Pairs of indices, generated in the same order as the lists of allowed pairs
    indices = combinations(range(n), r=2)
    # Current list of possible combinations. None means no information for this index
    current = [[None] * n]

    for (first, last), allowed in zip(indices, pairs_list):
        previous = current
        current = []
        # Iteration on each allowed pair for the current pair of indices
        for i, j in allowed:
            for comb in previous:
                if comb[first] is None:
                    # We can have previous combinations having None for the starting index 
                    # only during the first step. In this case, we create the path. 
                    new = comb[:]
                    new[first] = i
                    new[last] = j
                    current.append(new)
                if comb[first] == i:
                    if comb[last] is None:
                        # A path leading to a yet unknown value, we add it
                        new = comb[:]
                        new[last] = j
                        current.append(new)
                    elif comb[last] == j:
                        # A valid path, we keep it
                        current.append(comb[:])
                    # At this point, any previous combination that didn't satisfy 
                    # any rule of this turn hasn't made it
                    # to current and will be forgotten...
    return current

对您的数据运行示例:

possible_combs(3, [[(1,2), (1,3), (2,2)],
                    [(2,2), (1,2), (2,4)],
                    [(1,2), (4,3), (2,2)]])

输出:

[[2, 2, 2], [1, 2, 2]]

请注意，它不对每对索引的规则数量做出假设。