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

user_16941929 0
Viewed 176

I have the following Data, each letter of the Alphabet:

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

My goal is to get the maximum number of permutations of a length of 5, with the following 3 conditions:

  1. No letter shall be repeated more than once in each permutation.
  2. No permutation shall share more than 3 letters in common with another permutation in any position.
  3. No permutation shall share more than 2 adjacent letters in common in an identical position with another permutation.

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.

I have tried two different approaches to solve this task - using itertools with if conditions and mixed integer programming.

In terms of using itertools, I was not able to successfully define the conditions. I tried the following style of approach, with no luck:

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)

While with mixed integer programming, I was not able to wrap my head around the objective function, as I was not minimizing or maximizing anything. Furthermore, mixed integer programming would only give me 1 permutation that fits with the constraints.

combinations permutation itertools python
1 Answers

Can you please check if that solution matches your expectations? If so, I can provide some explanation.

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)
user_98592130
Related