На этом шаге мы рассмотрим пример, реализующий такой подход.

Вместо проверки правильности частичного решения путём перебора его первых i значений (они должны отличаться от elements[k]) код в примере 12.4 использует дополнительный параметр - логический список available размера n, в котором хранятся признаки доступности элементов исходного множества для включения их в частичное решение. Поэтому в методе-оболочке всем его п элементам изначально присваивается значение True.

Пример 12.4. Альтернативная печать всех перестановок элементов множества в списке

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

def generate_permutations_alt(i, available, sol, elements):
    # Базовый вариант
    if i == len(elements):
        print_permutations(sol)  # комплексное решение
    else:
        # Генерация элементов-кандидатов
        for k in range(0, len(elements)):

            # Проверка валидности кандидатов
            if available[k]:

                # Включить кандидата в частное решение
                sol[i] = elements[k]

                # k-й кандидат больше не доступен
                available[k] = False

                # Генерация элемента в позиции i+1
                generate_permutations_alt(i + 1, available,  
                                          sol, elements)

                # k-й кандидат снова доступен
                available[k] = True


def generate_permutations_alt_wrapper(elements):
    available = [True] * (len(elements))
    sol = [None] * (len(elements))
    generate_permutations_alt(0, available, sol, elements)


def print_permutations(sol):
    for i in range(0, len(sol)):
        print(sol[i], ' ', end='')
    print()

Архив с файлом можно взять здесь.

В этом случае условие в строке 10 становится гораздо проще и может быть оценено по времени как Θ(1). Таким образом, если элемент k действительно доступен, процедура сначала включает его в частичное решение (строка 13) и делает его недоступным (строка 16), а затем уже вызывает саму себя с увеличением параметра i (строки 19 и 20). По завершении вызова выбранный кандидат снова должен стать доступным для включения в частичное решение (строка 23). Обратите внимание, что по завершении рекурсивного вызова метод может выполнить несколько больше итераций цикла, чтобы вставить другие элементы в позицию i частичного решения, но перед этим список available должен быть приведён к своему начальному состоянию. В частности, available[k] должен быть установлен в True, так как алгоритму ещё придётся включать elements[k] в следующие позиции частичного решения. В итоге, несмотря на дополнительный входной параметр, этот алгоритм эффективнее алгоритма из примера 12.3.

На следующем шаге мы рассмотрим задачу n ферзей.

Предыдущий шаг Содержание Следующий шаг