Небольшой код для перемешивания с помощью порождающего элемента.
Математическое обоснование основано на теории групп.
Кратко:
В конечном поле, мощностью равному простому числу p есть мультипликативная группа, которая включает в себя все элементы кроме нуля.
В этой мультипликативной группе обязательно есть порождающий элемент.
Что такое порождающий элемент? Это элемент (a), который можно последовательно возводить в степень и получить все элементы мультипликативной группы, то есть все элементы нашего поля, кроме нуля. Причём единица получится всегда последней. a^(p-1) = 1 (mod p)
На том, что степени порождающего элемента проходят все элементы ровно по одному разу и построен предложенный алгоритм генерации перестановок. Он не годится для реальных дел, но в некоторых научных или ненаучных целях его можно использовать.
Нужно взять простое число большее как минимум на 2 максимальной длины строки.
0 в результате умножения не получается, а 1 будем считать признаком завершения подсчётов, элементы больше длины строки + 2 будем пропускать.
Для поиска порождающих элементов нужно разложить число (p-1) на множители. Если элемент a является порождающим, то возведение его в степени полученных множителей не должно равняться 1 по модулю p.
Как только один порождающий элемент найден, то порождающими будут его степени, взаимно простые с (p-1).
Для примера взял число 19. (19-1)=18=2*3*3
Проверяем число 2: 2^2 = 4≢1(mod p) 2^3 = 8≢1(mod p) - значит 2 - порождающий элемент.
Числа 1, 5, 7, 11, 13, 17 - взаимно простые с 18, поэтому 2^1, 2^5, 2^7, 2^11, 2^13, 2^17 - порождающие элементы
Это числа 2, 3, 10, 13, 14, 15. В данном случае у нас получится 6 вариантов перемешивания.
И теперь код:
public static void Main()
{
var str = "abcdefghijklmnop";
Console.WriteLine(str);
Console.WriteLine(string.Concat(Shuffle(str)));
}
private static Random Rnd = new Random((int)DateTime.Now.Ticks);
public static IEnumerable<char> Shuffle(string str)
{
var prime = 19;
var makers = new [] {2, 3, 10, 13, 14, 15};
var maker = makers[Rnd.Next(makers.Length)];
if(prime < str.Length + 2) throw new Exception("Слишком длинная строка");
var current = maker;
while(current != 1)
{
if(current < str.Length + 2)
yield return str[current - 2];
current *= maker;
current %= prime;
}
}
