Генерация перестановок. Алгоритм Джонсона‐Троттера - EcsFlash/DataTypes GitHub Wiki

Начнем с перестановок. Для простоты будем считать, что множество переставляемых элементов — это просто множество целых чисел от 1 до n. В общем случае их можно интерпретировать как индексы элементов n-элементного множества {a₁, ..., aₙ}. Как будет выглядеть применение метода умножения размера к задаче о генерации всех n! перестановок множества {1, ..., n}? Задача меньшего на единицу размера состоит в генерации всех (n - 1)! перестановок. Полагая, что задача меньшего размера успешно решена, мы можем получить решение большей задачи путем вставки n в каждую из n возможных позиций среди элементов каждой из перестановок n - 1 элементов. Все получаемые таким образом перестановки будут различны (почему?), а их общее количество будет равно n (n - 1)! = n!. Следовательно, таким образом мы получим все перестановки множества {1, ..., n}.

Мы можем вставлять n в ранее сгенерированных перестановках слева направо или справа налево. Как оказывается, выгодно начинать вставку n в последовательность 12 ... (n - 1) справа налево и изменять направление всякий раз при переходе к новой перестановке множества {1, ..., n - 1}.

Преимущество такого порядка генерации перестановок связано с тем фактом, что этот порядок удовлетворяет так называемому требованию минимальных изменений (minimal-change requirement): каждая перестановка получается из своей непосредственной предшественницы при помощи обмена местами только двух элементов. Требование минимальных изменений выгодно как с точки зрения скорости работы алгоритма, так и для приложений, которое будет использовать сгенерированные перестановки.

Можно получить тот же порядок перестановок n элементов и без явной генерации перестановок для меньших значений n. Это можно сделать, связав с каждым компонентом k перестановки направление. Будем указывать это направление при помощи стрелки над рассматриваемым элементом, например:

←  →  ←  ←
3  2  4  1

Компонент k в такой перестановке с использованием стрелок называется мобильным (mobile), если стрелка указывает на меньшее соседнее число. Например, в перестановке

→  ←  →  ←
3  2  4  1 

числа 3 и 4 мобильны, а 2 и 1 — нет. Воспользовавшись понятием мобильного элемента, мы получаем следующее описание так называемого алгоритма Джонсона–Троттера (Johnson–Trotter algorithm) для генерации перестановок.

АЛГОРИТМ JohnsonTrotter(n)
  // Реализация алгоритма Джонсона–Троттера
  // для генерации перестановок

  // Входные данные: Натуральное число n
  // Выходные данные: Список перестановок множества {1, ..., n}
                                               ←  ←       ←
  Инициализируем первую перестановку значением 1  2  ...  n

  while (есть мобильное число k) do
    Находим наибольшее мобильное число k
    Меняем местами k и соседнее целое число, на которое указывает стрелка у k
    Меняем направление стрелки у всех целых чисел, больших k

Вот пример использования этого алгоритма для n = 3 (наибольшее мобильное число показано полужирным шрифтом):

← ← ←
1 2 3

← ← ←
1 3 2

← ← ←
3 1 2

→ ← ←
3 2 1

← → ←
2 3 1

← ← →
2 1 3

Этот алгоритм — один из наиболее эффективных для генерации перестановок и может быть реализован со временем работы, пропорциональным количеству перестановок, т.е. Θ(n!). Конечно, он очень медленный для всех значений n, кроме самых малых, но это беда не алгоритма, а задачи, которая требует от алгоритма генерации слишком большого количества элементов.

Ну вот код на плюсах, но это полный пиздец:

void generatePermutationsJohnsonTrotter(int n) {
    vector<int> permutation(n);
    vector<bool> direction(n, false); // false - влево, true - вправо

    // Инициализация начальной перестановки (1, 2, ..., n)
    for (int i = 0; i < n; ++i) {
        permutation[i] = i + 1;
    }

    auto printPermutation = [](const vector<int>& perm) {
        for (int num : perm) {
            cout << num << " ";
        }
        cout << endl;
    };

    printPermutation(permutation);

    while (true) {
        // Шаг 1: Найти наибольший подвижный элемент
        int mobile = -1;
        int mobilePos = -1;
        for (int i = 0; i < n; ++i) {
            if (direction[i] == false && i > 0) {
                if (permutation[i] > permutation[i - 1]) {
                    if (permutation[i] > mobile) {
                        mobile = permutation[i];
                        mobilePos = i;
                    }
                }
            }
            if (direction[i] == true && i < n - 1) {
                if (permutation[i] > permutation[i + 1]) {
                    if (permutation[i] > mobile) {
                        mobile = permutation[i];
                        mobilePos = i;
                    }
                }
            }
        }

        if (mobile == -1) {
            break; // Нет подвижных элементов — завершение
        }

        // Шаг 2: Поменять местами с соседом в направлении
        if (direction[mobilePos] == false) {
            swap(permutation[mobilePos], permutation[mobilePos - 1]);
            swap(direction[mobilePos], direction[mobilePos - 1]);
            mobilePos--;
        } else {
            swap(permutation[mobilePos], permutation[mobilePos + 1]);
            swap(direction[mobilePos], direction[mobilePos + 1]);
            mobilePos++;
        }

        // Шаг 3: Изменить направление всех элементов, больших mobile
        for (int i = 0; i < n; ++i) {
            if (permutation[i] > mobile) {
                direction[i] = !direction[i];
            }
        }

        printPermutation(permutation);
    }
}