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

От моего ответа до другого вопроса:

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

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

Я записал об этом в намного большем количестве деталей здесь.

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

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

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

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

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

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

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

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

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

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

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

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

Это может быть изменено для использования целых чисел произвольной точности и наборов битов при помощи вызовов к соответствующим библиотекам вместо этого, и вышеупомянутые границы на самом деле начнут умирать, вместо того, чтобы ограничиваться в N=8, портативно (интервал может совпасть с коротким, и всего 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);
    }
}