有没有办法在相邻元素唯一的条件下得到所有排列？

Question

我有以下数据，字母表中的每个字母：

Letters = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 
           'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']

我的目标是获得长度为 5 的最大排列数，并满足以下 3 个条件：

1. 每个排列中字母不得重复一次以上。
2. 任何排列在任何位置上都不得与另一个排列共享超过 3 个相同的字母。
3. 任何排列不得与另一个排列在相同位置共享超过 2 个相同的相邻字母。

例如排列['A', 'B', 'C', 'D', 'E'] 和 ['A', 'B', 'F',不应允许使用“G”、“H”]，因为相同的“A”和“B”在两种排列中都是相邻的。但是，排列 ['A', 'B', 'C', 'D', 'E'] 和 ['A', 'F', 'B', 'G ', 'H'] 应该被允许。

每个排列有 5 个元素，[元素 1、元素 2、元素 3、元素 4、元素 5]。元素 1 的邻居仅是元素 2。元素 2 的邻居是元素 1 和元素 3。对于每个排列，相邻对为：[1, 2], [2, 3], [3, 4] ，[4, 5]。任何排列都不应与另一个 IF 具有相同的相邻对，并且仅当它们位于相同的元素位置时。

另一个类似的示例：['A', 'B', 'C', 'D', 'E'] 和 ['A', 'B', 'F '、'G'、'H']。在两个排列的相邻对中，[Element 1, Element 2] 是 ['A', 'B']。由于它们在同一元素位置相同，因此该解决方案无效。

如果：['A', 'B', 'C', 'D', 'E'] 和 ['F', 'A', 'B' ，'G'，'H']。在此示例中，尽管它们都有相邻对 ['A', 'B']，但它们位于不同的元素位置 [Element 1, Element 2] 且分别是[元素2、元素3]。因此，它们对于该解决方案都是有效的。

我尝试了两种不同的方法来解决此任务 - 使用带有 if 条件的 itertools 和混合整数编程。

在使用 itertools 方面，我无法成功定义条件。我尝试了以下风格的方法，但没有运气：

from itertools import permutations
AllPermutations = list(permutations(Letters, 5))
ActualPermutations = []
for Permutation in AllPermutations:
    if Permutation[0:2] not in [Permutation[0:2] for Permutation in ActualPermutations]:
        ActualPermutations.append(Permutation)

在使用混合整数编程时，我无法理解目标函数，因为我没有最小化或最大化任何东西。此外，混合整数规划只会给我 1 个符合约束的排列。

Answer 1

您能检查一下该解决方案是否符合您的期望吗？如果是这样，我可以提供一些解释。

from itertools import combinations


def three_letters_sub_set(letters):
    return combinations(letters, 3)

def adjacent_letters_sub_set(letters):
    for position in range(len(letters) - 1):
        adjacent_letters = (letters[position], letters[position + 1])
        yield position, adjacent_letters

def fails_rule2(letters):
    return any(
        three_letters in existing_three_letter_tuples
        for three_letters in three_letters_sub_set(letters)
    )

def fails_rule3(letters):
    for position, adjacent_letters in adjacent_letters_sub_set(letters):
        if adjacent_letters in existing_adjacent_letters[position]:
            return True
    return False

n_letters = 5
existing_three_letter_tuples = set()
existing_adjacent_letters = {position: set() for position in range(n_letters - 1)}

for comb in combinations(Letters, n_letters):
    if fails_rule2(comb):
        continue
    if fails_rule3(comb):
        continue

    existing_three_letter_tuples.update(three_letters_sub_set(comb))
    for position, adjacent_letters in adjacent_letters_sub_set(comb):
        existing_adjacent_letters[position].add(adjacent_letters)

    print(comb)