主页 / user-13907673

StrayByteIncarnate's questions

Martin Hope
StrayByteIncarnate
Asked: 2024-11-13 03:34:22 +0800 CST
  • 8

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

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_letter_dict = {1:['a','b','c'], 2:['c','d'], 3:['b','c']}

# create the edges based on the connections in the number_letter_dict
all_edges_array = []
for key in number_letter_dict.keys():
    for item in number_letter_dict[key]:
        all_edges_array.append([key, item])

# get the number of connections relative to the number of keys in dict
number_of_connections = len(number_letter_dict.keys())

# 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:
    duplicated_item = False
    seen_indices = []
    for item in collection:
        if item[0] in seen_indices:
            duplicated_item = True
            break
        if item[1] in seen_indices:
            duplicated_item = True
            break
        seen_indices.append(item[0])
        seen_indices.append(item[1])
    # all clear--add the collection! :)
    if not duplicated_item:
        all_good_combinations.append(collection)

这可行，但效率低下——对于我的实际输入，它需要花费令人无法接受的长时间才能运行。生成的组合比有效组合多得多，而且边和连接越多，情况就越糟。

我该如何改进这个算法？我假设它首先涉及不生成无效组合，但我看不出有办法实现这一点。

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

编辑：我替换了一些最小化的代码，因为它造成的混乱比它节省的还多：哎呀？此外，此代码确实有效。如果有足够的时间，它将可靠地给出正确答案。话虽如此，花五天时间处理一张图片对我来说还不够快。

python