主页 / coding / 问题 / 79182496
Accepted
StrayByteIncarnate
Asked: 2024-11-13 03:34:22 +0800 CST

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

  • 772

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

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

6 个回答

  1. Best Answer

    当您可以有选择地生成想要的组合时，生成所有组合并丢弃不需要的组合总是低效的。

    通过递归产生未使用的字母与当前递归级别的数字配对的组合，可以最有效地生成所需的组合，其中可以使用一个集合来跟踪已使用的字母：

    def unique_combinations(number_letter_dict):
    def _unique_combinations(index):
        if index == size:
            yield ()
            return
        number, letters = number_letters[index]
        for letter in letters:
            if letter not in used_letters:
                used_letters.add(letter)
                for combination in _unique_combinations(index + 1):
                    yield [number, letter], *combination
                used_letters.remove(letter)
    number_letters = list(number_letter_dict.items())
    size = len(number_letters)
    used_letters = set()
    return list(_unique_combinations(0))

    以便：

    number_letter_dict = {1: ['a', 'b', 'c'], 2: ['c', 'd'], 3: ['b', 'c']}
print(unique_combinations(number_letter_dict))

    输出：

    [([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'])]

    演示： https: //ideone.com/FfZwod

    • 2

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

    基本上，首先要形成一个从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')]]

    现在来看看上面的注释。根据来源的布局方式，您可能只看下一个数字。因此，如果您的所有来源在数字上都增加了 1，那么您只需添加 +1 而不必列出来源。

    • 1

  3. 你丢弃并忽略了字典中已有的结构。我们可以改用其值的乘积，这样可以避免无意义地生成和过滤具有相等数字的组合。只是仍然需要检查字母。

    from itertools import product

number_letter_dict = {1:['a','b','c'], 2:['c','d'], 3:['b','c']}

all_good_combinations = [
    list(zip(number_letter_dict, letters))
    for letters in product(*number_letter_dict.values())
    if len(set(letters)) == len(number_letter_dict)
]

for c in all_good_combinations:
    print(c)

    输出（在线尝试！）：

    [(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

  4. 如果您想要长度的组合comb_length，它们必须包含完全comb_length不同的数字。

    我们首先生成这些数字的所有可能组合（在 中all_combinations）。

    然后，对于这些数字组合中的每一个，我们递归地生成可能的组合（在 中edge_combinations），跟踪我们使用的字母和当前数字的索引。使用生成器，我们可以逐个生成组合，当我们有最后一个数字的剩余字母时，反向构建它们。

    from collections import defaultdict
from itertools import combinations


def edge_combinations(letters_for_nums, nums, max_num_idx, used_letters=set(), curr_idx=0):
    available_letters = letters_for_nums[nums[curr_idx]] - used_letters
    
    # If there are no available letters left, we abandon this path immediately
    if not available_letters:
        return

    num = nums[curr_idx]

    if curr_idx==max_num_idx:
        # We have available letters for the last number, we start yielding from the end
        for letter in available_letters:
            yield [[num, letter]]
    else: 
        for letter in available_letters:
            for subcomb in edge_combinations(letters_for_nums, nums, max_num_idx,
                                             used_letters=used_letters | {letter},
                                             curr_idx = curr_idx+1):
                yield [[num, letter]] + subcomb


def all_combinations(edges, comb_length):
    # We build a dict {number: set of corresponding letters}
    letters_for_nums = defaultdict(set)
    for num, letter in edges:
        letters_for_nums[num].add(letter)
    
    # And make a list of numbers:
    all_nums = [num for num in letters_for_nums]

    # We try all combinations of comb_length of these numbers
    for nums in combinations(all_nums, r=comb_length):
        yield from edge_combinations(letters_for_nums, nums, max_num_idx=comb_length-1)

    示例运行

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

for c in all_combinations(edges, 3):
    print(c)

    输出

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

    通过长度为 2 的组合，我们将得到：

    [[1, 'a'], [2, 'c']]
[[1, 'a'], [2, 'd']]
[[1, 'b'], [2, 'c']]
[[1, 'b'], [2, 'd']]
[[1, 'c'], [2, 'd']]
[[1, 'a'], [3, 'b']]
[[1, 'a'], [3, 'c']]
[[1, 'b'], [3, 'c']]
[[1, 'c'], [3, 'b']]
[[2, 'c'], [3, 'b']]
[[2, 'd'], [3, 'b']]
[[2, 'd'], [3, 'c']]
    • 0

  5. 你可以将其视为一个图形问题，而不是组合问题。你的all_edges例子是相邻节点共享一个字母或数字的图形：

          3b
     /  \
   1b    3c
  /  \  /  \
1a -- 1c -- 2c -- 2d

    该图有助于识别原始图的分区，其中分区之间不共享数字和字母，因为一旦选择了一个节点，其所有邻居就不再有资格。

    一种可能的分区方法是找到所有高度为 5 的树。然后对于每棵树，第 1、第 3 和第 5 级构成一个有效分区，因为第 2 和第 4 级将它们分开。

    对于每个分区，调用itertools.product()以生成所有解决方案。可能会有一些重复，但不应该太多。

    • 0 
  6. def find unique combinations(pairs):
    # Helper function to check if a combination is valid
    def is_valid_combination(combo):
        first_elements = set()
        last_elements = set()
        for pair in combo:
            if pair[0] in first_elements or pair[1] in last_elements:
                return False
            first_elements.add(pair[0])
            last_elements.add(pair[1])
        return True

    # Recursive function to generate combinations
    def generate_combinations(index, current_combo):
        # If the current combination is valid, store it
        if is_valid_combination(current_combo):
            results.append(list(current_combo))

        # Iterate over remaining pairs to form new combinations
        for i in range(index, len(pairs)):
            current_combo.append(pairs[i])
            generate_combinations(i + 1, current_combo)
            current_combo.pop()

    results = []
    • -1

相关问题