Итерация перетасована [0..n) без массивов

Я знаю несколько подпрограмм, которые работают следующим образом:

X _{n + 1}= Routine (X _n, max)

Например, что-то вроде генератора LCG:

X _{n + 1}= (a * X _n + c) mod m

Недостаточно параметризации в этом генераторе для генерации каждой последовательности.

Функция мечты:

X _{n + 1}= Routine (X _n, max, номер перестановки)

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

В противном случае у кого-нибудь есть указатели на аналогичные функции, которые либо без гражданства, либо имеют постоянное количество состояний для произвольного "max", так что они будут перебирать перетасованный список.

Ответы

Ответ 1

Есть n! перестановки n элементов. Хранение того, который вы используете, требует, по крайней мере, log (n!)/Log (2) бит. По приближению Стирлинга это берет приблизительно n log (n)/log (2) бит.

Явное хранение одного индекса принимает бит log (n)/log (2). Сохранение всех n, как в массиве индексов, занимает в n раз больше, или снова n log (n)/log (2). Информационно-теоретически нет лучшего способа, чем явное сохранение перестановки.

Другими словами, индекс, который вы передаете, в какой перестановке в нужном вам наборе занимает такое же асимптотическое пространство для хранения, как просто запись перестановки. Если, например, вы ограничиваете индекс перестановки 32-битными значениями, вы можете обрабатывать только перестановки до 12 элементов. 64-разрядные индексы позволяют получить до 20 элементов.

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

Ответ 2

Из моего ответа на еще один вопрос:

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

Выберите блок-шифр, например TEAили XTEA. Используйте XOR folding для уменьшите размер блока до наименьшего мощность двух больше заданной вы выбираете. Используйте случайную семя как ключ к шифру. к порождают элемент n в перестановка, шифрование n с помощью шифр. Если номер выхода не указан ваш набор, зашифруйте это. Повторяйте до число внутри набора. На в среднем вам придется делать меньше, чем два шифрования на сгенерированное число. Это имеет дополнительное преимущество, если ваше семя криптографически безопасно, так и вся ваша перестановка.

Я писал об этом гораздо подробнее здесь.

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

Ответ 3

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

X(n+1) = Routine(Xn, max, permutation number)
for(i = n; i > 0; i--)
 {
   int temp = Map.lookup(i) 
   otherfun(temp,max,perm)
 }

Ответ 4

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

Отказ от ответственности: я, возможно, неправильно понял ваш вопрос...

Ответ 5

Код, который распаковывает индекс перестановки в массив с определенным отображением от индекса к перестановке. Есть множество других, но это удобно.

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

typedef unsigned char index_t;
typedef unsigned int permutation;

static void permutation_to_array(index_t *indices, index_t n, permutation p)
{
    index_t used = 0;
    for (index_t i = 0; i < n; ++i) {
        index_t left = n - i;
        index_t digit = p % left;
        for (index_t j = 0; j <= digit; ++j) {
            if (used & (1 << j)) {
                digit++;
            }
        }
        used |= (1 << digit);
        indices[i] = digit;
        p /= left;
    }
}

static void dump_array(index_t *indices, index_t n)
{
    fputs("[", stdout);
    for (index_t i = 0; i < n; ++i) {
        printf("%d", indices[i]);
        if (i != n - 1) {
            fputs(", ", stdout);
        }
    }
    puts("]");
}

static int factorial(int n)
{
    int prod = 1;
    for (int i = 1; i <= n; ++i) {
        prod *= i;
    }
    return prod;
}

int main(int argc, char **argv)
{
    const index_t n = 4;
    const permutation max = factorial(n);
    index_t *indices = malloc(n * sizeof (*indices));
    for (permutation p = 0; p < max; ++p) {
        permutation_to_array(indices, n, p);
        dump_array(indices, n);
    }
    free(indices);
}

Ответ 6

Код, который использует итерационный интерфейс. Сложность по времени - O (n ^ 2). Сложность пространства имеет накладные расходы: копия n (log n бит), итерационная переменная (log n bits), отслеживание ni (log n bits), копия текущего значения (log n bits), копия p (n log n бит), создание следующего значения (log n bits) и бит набора используемых значений (n бит). Вы не можете избежать накладных расходов на n log n бит. С другой стороны, это также O (n ^ 2), для установки бит. Это можно уменьшить немного, но ценой использования украшенного дерева для хранения используемых значений.

Это может быть изменено для использования произвольных целых чисел точности и наборов бит, используя вместо этого вызовы в соответствующие библиотеки, и вышеприведенные оценки фактически начнут удары, а не будут ограничены N = 8, переносимо (int может быть такой же, как короткий, и до 16 бит). 9!= 362880 > 65536 = 2 ^ 16

#include <math.h>
#include <stdio.h>

typedef signed char index_t;
typedef unsigned int permutation;

static index_t permutation_next(index_t n, permutation p, index_t value)
{
    permutation used = 0;
    for (index_t i = 0; i < n; ++i) {
        index_t left = n - i;
        index_t digit = p % left;
        p /= left;
        for (index_t j = 0; j <= digit; ++j) {
            if (used & (1 << j)) {
                digit++;
            }
        }
        used |= (1 << digit);
        if (value == -1) {
            return digit;
        }
        if (value == digit) {
            value = -1;
        }
    }
    /* value not found */
    return -1;
}

static void dump_permutation(index_t n, permutation p)
{
    index_t value = -1;
    fputs("[", stdout);
    value = permutation_next(n, p, value);
    while (value != -1) {
        printf("%d", value);
        value = permutation_next(n, p, value);
        if (value != -1) {
            fputs(", ", stdout);
        }
    }
    puts("]");
}

static int factorial(int n)
{
    int prod = 1;
    for (int i = 1; i <= n; ++i) {
        prod *= i;
    }
    return prod;
}

int main(int argc, char **argv)
{
    const index_t n = 4;
    const permutation max = factorial(n);
    for (permutation p = 0; p < max; ++p) {
        dump_permutation(n, p);
    }
}