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

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个条件：

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

e.g. Permutations ['A', 'B', 'C', 'D', 'E'] and ['A', 'B', 'F', 'G', 'H'] should not be permitted as the same 'A' and 'B' are adjacent in both permutations. However, permutations ['A', 'B', 'C', 'D', 'E'] and ['A', 'F', 'B', 'G', 'H'] should be permitted.

Each permutation has 5 elements, [Element 1, Element 2, Element 3, Element 4, Element 5]. The neighbours of Element 1 is only Element 2. The neighbours of Element 2 is Element 1 and Element 3. For each permutation the neighbouring pairs are: [1, 2], [2, 3], [3, 4], [4, 5]. No permutation should have the same neighbouring pair as another IF and only if they are in the same element position.

Another similar example: ['A', 'B', 'C', 'D', 'E'] and ['A', 'B', 'F', 'G', 'H']. In the neighbouring pair of both permutations, [Element 1, Element 2] is ['A', 'B']. As they are identical at the same Element location, the solution is not valid.

If however: ['A', 'B', 'C', 'D', 'E'] and ['F', 'A', 'B', 'G', 'H']. In this example, although they both have a neighbouring pair ['A', 'B'], they are found in different Element locations [Element 1, Element 2] and [Element 2, Element 3] respectively. Therefore, they are both valid for the solution.

我尝试了两种不同的方法来解决此任务 - 使用 itertools 和 if 条件以及混合整数规划。

在使用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)

虽然使用混合整数规划，但我无法全神贯注于 objective 函数，因为我没有最小化或最大化任何东西。此外，混合整数规划只会给我 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)

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

Is there a way to get all permutations with the condition of unique adjacent elements?

python

combinations

permutation

itertools