Как сгенерировать псевдослучайную инволюцию?

Давайте здесь используем a(n) как количество инволюций в наборе размером n (как это делает OEIS). Для данного набора размера n и данного элемента в этом наборе общее количество инволюций в этом наборе равно a(n). Этот элемент должен быть либо неизменен при инволюции, либо заменен другим элементом. Количество инволюций, которые оставляют наш элемент фиксированным, равно a(n-1), так как это инволюции на других элементах. Следовательно, равномерное распределение инволюций должно иметь вероятность a(n-1)/a(n) сохранения этого элемента фиксированным. Если это должно быть исправлено, просто оставьте этот элемент в покое. В противном случае выберите другой элемент, который еще не был проверен нашим алгоритмом, чтобы заменить его нашим элементом. Мы только что решили, что произойдет с одним или двумя элементами в наборе: продолжайте и решайте, что происходит с одним или двумя элементами одновременно.

Для этого нам нужен список счетчиков инволюций для каждого i <= n, но это легко сделать с помощью формулы рекурсии

a(i) = a(i-1) + (i-1) * a(i-2)

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

# Counts of involutions (self-inverse permutations) for each size
_invo_cnts = [1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152]

def invo_count(n):
    """Return the number of involutions of size n and cache the result."""
    for i in range(len(_invo_cnts), n+1):
        _invo_cnts.append(_invo_cnts[i-1] + (i-1) * _invo_cnts[i-2])
    return _invo_cnts[n]

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

Вот код на Python 3.5.2. Код несколько усложнен из-за косвенности, связанной со списком неопределившихся элементов.

from random import randrange

def randinvolution(n):
    """Return a random (uniform) involution of size n."""

    # Set up main variables:
    # -- the result so far as a list
    involution = list(range(n))
    # -- the list of indices of unseen (not yet decided) elements.
    #    unseen[0:cntunseen] are unseen/undecided elements, in any order.
    unseen = list(range(n))
    cntunseen = n

    # Make an involution, progressing one or two elements at a time
    while cntunseen > 1:  # if only one element remains, it must be fixed
        # Decide whether current element (index cntunseen-1) is fixed
        if randrange(invo_count(cntunseen)) < invo_count(cntunseen - 1):
            # Leave the current element as fixed and mark it as seen
            cntunseen -= 1
        else:
            # In involution, swap current element with another not yet seen
            idxother = randrange(cntunseen - 1)
            other = unseen[idxother]
            current = unseen[cntunseen - 1]
            involution[current], involution[other] = (
                involution[other], involution[current])
            # Mark both elements as seen by removing from start of unseen[]
            unseen[idxother] = unseen[cntunseen - 2]
            cntunseen -= 2

    return involution

Я сделал несколько тестов. Вот код, который я использовал для проверки правильности и равномерного распределения:

def isinvolution(p):
    """Flag if a permutation is an involution."""
    return all(p[p[i]] == i for i in range(len(p)))

# test the validity and uniformness of randinvolution()
n = 4
cnt = 10 ** 6
distr = {}
for j in range(cnt):
    inv = tuple(randinvolution(n))
    assert isinvolution(inv)
    distr[inv] = distr.get(inv, 0) + 1
print('In {} attempts, there were {} random involutions produced,'
    ' with the distribution...'.format(cnt, len(distr)))
for x in sorted(distr):
    print(x, str(distr[x]).rjust(2 + len(str(cnt))))

И результаты были

In 1000000 attempts, there were 10 random involutions produced, with the distribution...
(0, 1, 2, 3)     99874
(0, 1, 3, 2)    100239
(0, 2, 1, 3)    100118
(0, 3, 2, 1)     99192
(1, 0, 2, 3)     99919
(1, 0, 3, 2)    100304
(2, 1, 0, 3)    100098
(2, 3, 0, 1)    100211
(3, 1, 2, 0)    100091
(3, 2, 1, 0)     99954

Мне это кажется довольно однородным, как и другие результаты, которые я проверял.

Инволюция — это взаимно однозначное отображение, обратное самому себе. Любой шифр представляет собой взаимно однозначное отображение; это должно быть для того, чтобы зашифрованный текст был однозначно расшифрован.

Для инволюции вам нужен шифр, который является обратным самому себе. Такие шифры существуют, например, ROT13. См. Взаимный шифр для некоторых других.

На ваш вопрос я бы предложил шифр XOR. Выберите случайный ключ, длина которого не меньше длины самого длинного фрагмента данных в исходном наборе данных. Если вы используете 32-битные числа, используйте 32-битный ключ. Чтобы переставить, XOR ключа с каждым фрагментом данных по очереди. Обратная перестановка (эквивалентная расшифровке) — это точно такая же операция XOR, которая возвращает исходные данные.

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

ETA: Это демонстрация на Java того, о чем я говорю во втором комментарии. Будучи Java, я использую индексы 0..12 для вашего набора из 13 элементов.

public static void Demo() {

    final int key = 0b1001;

    System.out.println("key = " + key);
    System.out.println();

    for (int i = 0; i < 13; ++i) {

        System.out.print(i + " -> ");
        int ctext = i ^ key;

        while (ctext >= 13) {
            System.out.print(ctext + " -> ");
            ctext = ctext ^ key;
        }
        System.out.println(ctext);
    }

} // end Demo()

Вывод из демонстрации:

key = 9

0 -> 9
1 -> 8
2 -> 11
3 -> 10
4 -> 13 -> 4
5 -> 12
6 -> 15 -> 6
7 -> 14 -> 7
8 -> 1
9 -> 0
10 -> 3
11 -> 2
12 -> 5

Там, где преобразованный ключ упадет за конец массива, он снова преобразуется, пока не попадет в массив. Я не уверен, что конструкция while подпадает под строгое математическое определение функции.