如何找到对的所有组合，使得组合中没有元素具有共同的第一个或最后一个值？

Question

我有一个数字字母对列表，例如：

all_edges_array = [
                   [1,'a'],[1,'b'],[1,'c'],
                   [2,'c'],[2,'d'],
                   [3,'b'],[3,'c']
                  ]

请注意，输入对不是所使用的字母和数字的叉积 - 例如，缺少

[2, 'a']

。

我想有效地找到一些对的组合，这样在一个组中，没有两对使用相同的数字或相同的字母。

对于上述输入，总共应该有 5 个结果：

[([1, 'a'], [2, 'c'], [3, 'b']), ([1, 'a'], [2, 'd'], [3, 'b']), ([1, 'a'], [2, 'd'], [3, 'c']), ([1, 'b'], [2, 'd'], [3, 'c']), ([1, 'c'], [2, 'd'], [3, 'b'])]

。

其他组合无效：例如，

([1, 'a'], [1, 'b'], [3, 'c'])

包含两对使用相同数字 (1) 的组合，

([1, 'b'], [2, 'c'], [3, 'b'])

包含两对使用相同字母 (b) 的组合。

我有代码通过使用

itertools.combinations

来暴力破解，然后过滤结果：

from itertools import combinations

number_of_connections = 3

# Find all 35 combinations
all_combinations_array = list(combinations(all_edges_array, number_of_connections))

# cut down the list of combinations to what I actually need
all_good_combinations = []
for collection in all_combinations_array:
    # check if numbers are the same
    if collection[0][0] == collection[1][0] or collection[0][0] == collection[2][0] or collection[1][0] == collection[2][0]:
        continue
    # check if letters are the same
    if collection[0][1] == collection[1][1] or collection[0][1] == collection[2][1] or collection[1][1] == collection[2][1]:
        continue
    # all clear--add the collection! :)
    all_good_combinations.append(collection)

这可行，但效率低下——我的实际输入需要很长的时间才能运行。生成的组合比有效组合多得多，边缘和连接越多，情况只会变得更糟。

如何改进这个算法？我认为它首先不涉及生成无效的组合，但我没有找到实现这一点的方法。

我找到了之前的问答Python：如何生成元组列表的所有组合而不重复元组的内容，但它没有回答我的问题。那里的答案假设输入包含所有可能的对（并且组合中的对的数量应等于更受约束的对元素的可能性数量）。

Answer 1

你是对的，你的方式可能效率低下。我不确定您的实际输入，但是如果长度增加，初始解决方案（有效或无效）的数量将大幅增加。相反，您可以通过递归/回溯来解决这个问题。我通常讨厌回溯，但这似乎是一个很好的用例。

基本上首先从

int -> str

形成一个映射来了解

source -> dest

节点。这可以像这样完成：

for number, letter in all_edges_array:
    number_to_letters[number].append(letter)

现在如果我们想知道 1 附加到什么，我们可以这样做：

>>> number_to_letters[1]
['a', 'b', 'c']

接下来是实际的算法。基本上遍历直到达到长度 N，在本例中为 3。达到长度后，添加该列表的副本并返回。

如果您仍在构建列表，请查看下一个有效的源节点。请记住，我们实际上已经为映射中的源节点创建了岛。然后我们检查从下一个源连接的边，如果该目的地不在我们的“已用”集合中，那么我们可以添加它。然后我们就递归+回溯。

可以在下面完成：

sources = list(number_to_letters.keys())

def find_combinations(current_combination, used_letters, results):
    # If we've reached the target length, add to results
    if len(current_combination) == number_of_connections:
        results.append(current_combination[:])
        return

    # Find the next number to add a pair for
    # NOTE below
    next_idx = len(current_combination)
    if next_idx >= len(sources):
        return
    next_number = sources[next_idx]

    # Try each letter for the current number and make sure it's not used
    for letter in number_to_letters[next_number]:
        if letter not in used_letters:
            # Add the pair and recurse
            current_combination.append((next_number, letter))
            used_letters.add(letter)
            find_combinations(current_combination, used_letters, results)
            # Backtrack
            current_combination.pop()
            used_letters.remove(letter)

并运行它：

>>> find_combinations([], set(), results)
>>> results
[[(1, 'a'), (2, 'c'), (3, 'b')],
 [(1, 'a'), (2, 'd'), (3, 'b')],
 [(1, 'a'), (2, 'd'), (3, 'c')],
 [(1, 'b'), (2, 'd'), (3, 'c')],
 [(1, 'c'), (2, 'd'), (3, 'b')]]


Now for the NOTE above. Depending how your sources are laid out, you could potentially just look at the next number. So if your sources are all numerically increasing by 1, then you could just add +1 and not have to list the sources.