Генерация обратимых перестановок над множеством

Question

Я хочу пройти все элементы в наборе Q = [0, 2^16) непоследовательным образом. Для этого мне нужна функция f(x) Q -> Q, которая задает порядок, в котором набор будет отсортирован. например:

f(0) = 2345   
f(1) = 4364   
f(2) = 24   
(...)

Чтобы восстановить порядок, мне понадобится обратная функция f'(x) Q -> Q, которая выведет:

f(2345) = 0
f(4364) = 1
f(24) = 2
(...)

Функция должна быть биективной, для каждого элемента Q функция однозначно отображается на другой элемент Q.

Как я могу сгенерировать такую ​​функцию или есть какие-нибудь известные функции, которые делают это?

Answer 1

РЕДАКТИРОВАТЬ: В следующем ответе, f(x) это "что идет после х", а не "что идет в положении х". Например, если ваше первое число равно 5, то следующим элементом будет f(5), а не f(1). Оглядываясь назад, вы, вероятно, думали о f(x) как о "что идет в положении x". Функция, определенная в этом ответе, намного слабее, если ее использовать как "то, что идет в положении x".

---

Линейные конгруэнтные генераторы соответствуют вашим потребностям.

Линейный конгруэнтный генератор определяется уравнением

f(x) = a*x+c (mod m)

для некоторых констант a, c, а также m, В этом случае, m = 65536,

LCG имеет полный период (желаемое свойство), если выполняются следующие свойства:

1. c а также m относительно простые.
2. a-1 делится на все основные факторы m,
3. Если m кратно 4, a-1 кратно 4.

Мы пойдем с a = 5, c = 1,

Чтобы инвертировать LCG, мы решаем для f(x) с точки зрения x:

x = (a^-1)*(f(x) - c) (mod m)

Мы можем найти обратную величину 5 mod 65536 с помощью расширенного евклидова алгоритма, или, поскольку нам просто нужно это одно вычисление, мы можем подключить его к Wolfram Alpha. Результат 52429.

Таким образом, мы имеем

f(x) = (5*x + 1) % 65536
f^-1(x) = (52429 * (x - 1)) % 65536

Answer 2

Есть много подходов к решению этого.

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

Одним из подходов к созданию перестановки является отображение всех элементов в массиве, а затем случайная замена их "достаточно" раз. Код C:

int f[PERM_SIZE], inv_f[PERM_SIZE];
int i;

// start out with identity permutation
for (i=0; i < PERM_SIZE; ++i) {
    f[i] = i;
    inv_f[i] = i;
}

// seed your random number generator
srand(SEED);

// look "enough" times, where we choose "enough" = size of array
for (i=0; i < PERM_SIZE; ++i) {
    int j, k;
    j = rand()%PERM_SIZE;
    k = rand()%PERM_SIZE;
    swap( &f[i], &f[j] );
}

// create inverse of f
for (i=0; i < PERM_SIZE; ++i)
    inv_f[f[i]] = i;

наслаждаться