Итерация в случайном порядке [0..n) без массивов

Question

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

X_{n + 1} = Рутина (X_n, не более)

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

X_{n + 1} = (a * X_n + c) mod m

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

Функция сна:

X_{n + 1} = Рутина (X_n, макс., Номер перестановки)

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

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

Answer 1

Нет! перестановки из 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.

Answer 2

Из моего ответа на другой вопрос:

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

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

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

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

Answer 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)
 }

Answer 4

Код, который использует итеративный интерфейс. Сложность по времени составляет O(n^2), сложность пространства имеет служебные данные: копия n (log n битов), итерационная переменная (log n битов), отслеживание ni (log n битов), копия текущего значения (log n битов), копия p (n log n битов), создание следующего значения (log n битов) и набор битов используемых значений (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);
    }
}

Answer 5

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

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

Answer 6

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

#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);
}