Генерация перестановок с сублинейной памятью

Question

Мне интересно, существует ли достаточно простой алгоритм для генерации перестановок из N элементов, скажем, 1..N, который использует менее O(N) памяти. Это не должно быть вычисление n-й перестановки, но оно должно быть в состоянии вычислить все перестановки.

Конечно, этот алгоритм должен быть генератором какого-то рода или использовать некоторую внутреннюю структуру данных, которая использует менее O(N) памяти, поскольку возврат результата в виде вектора размером N уже нарушает ограничение линейная память.

Answer 1

Предположим, что случайная перестановка генерируется по одной записи за раз.Состояние генератора должно кодировать набор оставшихся элементов (выполнить его до завершения), и поэтому, поскольку никакая возможность не может быть исключена, состояние генератора составляет не менее n битов.

Answer 2

Может быть, вы можете, с факторическими номерами.Вы можете извлекать из него полученную перестановку шаг за шагом, так что вам никогда не придется хранить весь результат в памяти.

Но причина, с которой я начал, может быть, в том, что я не уверен, каково поведение растущего размера самого фактического числа.Если он вписывается в 32-битное целое число или что-то в этом роде, N будет ограничено константой, поэтому O (N) будет равно O (1), поэтому мы должны использовать для него массив, но я не уверен, насколько большим он будетбыть с точки зрения N.

Answer 3

Я думаю, что даже хранить ваш результат (который будет упорядоченным списком из N элементов) будет O (N) в памяти, нет?

В любом случае, чтобы ответить на ваш последующий вопрос о выборе перестановкинаугад, вот техника, которая будет лучше, чем просто производить все N!скажем, возможности в списке, а затем случайный выбор индекса.Если мы можем просто выбрать индекс случайным образом и сгенерировать из него соответствующую перестановку, нам будет намного лучше.

Мы можем представить порядок словаря для ваших слов / перестановок и связать с ним уникальное число на основепорядок появления слова / перестановки в словаре.Например, слова из трех символов были бы

   perm.              index
    012    <---->       0
    021    <---->       1
    102    <---->       2
    120    <---->       3
    201    <---->       4
    210    <---->       5

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

Чтобы выбрать случайный случайный случай, вы можете выбрать случайным образом связанный с ним индекс из диапазона 0 ... N! -1 с равномерной вероятностью (простейшая реализация этого явно исключена даже для умеренно большого N, я знаю, ноЯ думаю, что есть достойные обходные пути), а затем определить связанные с ним перестановки.Обратите внимание, что список начинается со всех перестановок последних N-1 элементов, сохраняя первую цифру равной 0. После того, как эти возможности исчерпаны, мы генерируем все те, которые начинаются с 1. После этих следующих (N-1)!Перестановки исчерпаны, мы генерируем те, которые начинаются с 2. И т.д. Таким образом, мы можем определить, что ведущая цифра - это Floor [R / (N-1)!], где R был индексом в смысле, показанном выше.Теперь вы поймете, почему мы тоже проиндексировали ноль?

Чтобы сгенерировать оставшиеся N-1 цифры в перестановке, скажем, что мы определили Floor [R / (N-1)!] = A0.Начните со списка {0, ..., N-1} - {a0} (установить вычитание).Нам нужна Q-я перестановка этого списка, для Q = R mod (N-1) !.За исключением учета того факта, что отсутствует пропущенная цифра, это то же самое, что и проблема, которую мы только что решили.Recurse.

Answer 4

Алгоритм C ++ next_permutation выполняет перестановку на месте последовательности в ее следующую перестановку или возвращает false, когда дальнейшие перестановки отсутствуют. Алгоритм выглядит следующим образом:

template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last) {
    if (first == last) return false; // False for empty ranges.
    BidirectionalIterator i = first;
    ++i;
    if (i == last) return false; // False for single-element ranges.
    i = last;
    --i;
    for(;;) {
        BidirectionalIterator ii = i--;
        // Find an element *n < *(n + 1).
        if (*i <*ii) {
            BidirectionalIterator j = last;
            // Find the last *m >= *n.
            while (!(*i < *--j)) {}
            // Swap *n and *m, and reverse from m to the end.
            iter_swap(i, j);
            reverse(ii, last);
            return true;
        }
        // No n was found.
        if (i == first) {
            // Reverse the sequence to its original order.
            reverse(first, last);
            return false;
        }
    }
}

При этом используется постоянное пространство (итераторы) для каждой сгенерированной перестановки. Вы считаете это линейным?

Answer 5

Я думаю, что ответом должно быть «нет».

Рассмотрим генератор перестановок N-элементов как конечный автомат: он должен содержать как минимум столько же состояний, сколько существует перестановок, иначе он будетначните повторять до того, как он завершит генерацию их всех.

Есть N!такие перестановки, которые потребуют по крайней мере биты ceil (log2 (N!)) для представления. Аппроксимация Стирлинга говорит нам, что log2 (N!) - это O (N log N), поэтому мы не сможем создать такой генератор с сублинейной памятью.