1.9 Комбинаторика

1.9.1 Основные комбинаторные конфигурации

1.9.2 Формулы пересчёта числа комбинаторных конфигураций

1.9.3 Перечисление перестановок

1.9.4 Приложения к теории вероятностей

 

Перечисление перестановок

Рассмотрим некоторые алгоритмы порождения (перечисления) последовательности всех перестановок n элементов.

  1. Лексикографическая (алфавитная). Последовательность определяется индуктивно: для каждой перестановки указан первый элемент, далее - все следующие за ним.
    1, (все перестановки из (2,.....,n} в алфавитном порядке)
    2, (все перестановки из {1, 3,....,n} в алфавитном порядке)
    3, (все перестановки из {1, 2, 4,.....,n} в алфавитном порядке)
    k, (все перестановки из {1,2,.....,k-1, k+ 1,..., n} в алфавитном порядке)
    n, (все перестановки из {1, 2,.....,n-1} в алфавитном порядке).

    Например, для n = 3:
    1,2,3
    1,3,2
    2,1,3
    3,1,2
    3,2,1

  2. Конфигурации (перестановки) располагаются в такой последовательности, что каждая (начиная со второй) отличается от предыдущей тем, что в ней поменялись местами ровно два элемента (такая ситуация и вместе с тем операция такой замены называется транспозицией). Такая последовательность перестановок может оказаться полезной, если при решении какой-то (например, комбинаторной) задачи с каждой перестановкой связаны некоторые вычисления и существует возможность использования частичных результатов, полученных для предыдущей перестановки, если последовательные перестановки мало отличаются друг от друга.
    Существуют различные алгоритмы построения таких последовательностей, удобные в тех или иных отношениях, в частности для программирования
  3. Частным случаем предыдущего можно считать последовательность, в которой разница между двумя соседними перестановками еще меньше: они различаются транспозицией двух соседних элементов. Идея такого алгоритма - индуктивное построение. Пусть уже построена обладающая этим свойством последовательность элементов 1, 2,..., (n-1). Тогда требуемую последовательность перестановок элементов 1, 2,..., n получим, вставляя т всеми возможными способами (их число равно n) в каждую из перестановок элементов 1, 2,..., (n-1) на различные места, передвигая n попеременно вперед и назад (n-1)! раз. Ниже идея алгоритма проиллюстрирована для n = 2, 3, 4 и (начало последовательности) для n = 5; элемент- n выделен жирным шрифтом; в каждом столбце отмечены транспозиции элементов 1, 2,.....,(n-1):

 

Таблица 3
n=2 n=3 n=4 n=5
1 2
2 1
1 2 3
1 3 2
3 1 2   12
3 2 1   21
2 3 1
2 1 3
1 2 3 4
1 2 4 3
1 4 2 3
4 1 2 3   23
4 1 3 2   32
1 4 3 2
1 3 4 2
1 3 2 4   13
3 1 2 4   31
3 1 4 2
3 4 1 2
4 3 1 2   12
4 3 2 1   21
3 4 2 1
3 2 4 1
3 2 1 4   32
2 3 1 4   23
2 3 4 1
2 4 3 1
4 2 3 1   31
4 2 1 3   13
2 4 1 3
2 1 4 3
2 1 3 4
1 2 3 4 5
1 2 3 5 4
1 2 5 3 4
1 5 2 3 4
5 1 2 3 4   34
5 1 2 4 3   43
1 5 2 4 3
1 2 5 4 3
1 2 4 5 3
1 2 4 3 5   24
1 4 2 3 5   42
1 4 2 5 3
1 4 5 2 3
1 5 4 2 3
5 1 4 2 3   14
5 4 1 2 3   41
4 5 1 2 3
4 1 5 2 3
4 1 2 5 3
4 1 2 3 5   23
4 1 3 2 5   32
4 1 3 5 2
4 1 5 3 2
4 5 1 3 2
5 4 1 3 2   41
5 1 4 3 2   14
1 5 4 3 2
......