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

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 个相同的相邻字母。

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.

我尝试了两种不同的方法来解决此任务 - 使用带有 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)