Алгоритм получения всех возможных комбинаций с ограничениями - PullRequest
Новая
       4

Алгоритм получения всех возможных комбинаций с ограничениями

0 голосов
/ 26 марта 2020

У меня есть цифры от 0 до 7. Возможная комбинация должна содержать все числа. Решение имеет 8 цифр. В дополнение к этому применяются следующие правила: 

0 comes before 1
1 comes before 3
2 comes before 3
4 comes before 5
6 comes before 7

Примеры решений: 01234567, 20134567

Неправильные решения: 01123456 или 31204567

Первый всего: поскольку это не упражнение из университета, а реальная проблема, с которой я столкнулся при написании настоящей программы, я даже не уверен, существует ли простое решение для этого. Но если есть, я был бы признателен за ответ.

1 Ответ

1 голос
/ 26 марта 2020

Чтобы сделать вещи более эффективными (и предположим, что решений гораздо меньше, чем перестановок), идея такова:

  • Генерация всех перестановок одна за другой.
  • Не интерпретировать перестановка в обычном порядке, но интерпретировать его как указание для каждого ди git, в какую позицию он будет go. Таким образом, с учетом перестановки (3, 2, 0, 1) интерпретируйте ее как 0, перейдите к положению 3, 1 перейдите к положению 2, 2 к положению 0, 3 к положению 1 (таким образом, обратная перестановка : (2, 3, 1, 0)). Тогда тест для принятия перестановки или нет, является гораздо более простым.

Вот реализация в Python, но ту же идею можно применить на любом языке программирования: 

from itertools import permutations

num = 0
q = [0 for _ in range(8)] # create a list to fit 8 values
for p in permutations(range(8)):
    if p[0] < p[1] < p[3] and p[2] < p[3] and p[4] < p[5] and p[6] < p[7]:
        for i, pi in enumerate(p):
            q[pi] = i
        num += 1
        print(num, q)

Выход: 

1 [0, 1, 2, 3, 4, 5, 6, 7]
2 [0, 1, 2, 3, 4, 6, 5, 7]
3 [0, 1, 2, 3, 4, 6, 7, 5]
4 [0, 1, 2, 3, 6, 4, 5, 7]
5 [0, 1, 2, 3, 6, 4, 7, 5]
6 [0, 1, 2, 3, 6, 7, 4, 5]
...
1257 [4, 6, 7, 5, 2, 0, 1, 3]
1258 [6, 4, 5, 7, 2, 0, 1, 3]
1259 [6, 4, 7, 5, 2, 0, 1, 3]
1260 [6, 7, 4, 5, 2, 0, 1, 3]
...