Очень давно я думаю над одной задачей, часть решения которой, содержит функцию своеобразного перемешивания некоторого массива данных. Суть перемешивания довольно проста: нужно из исходного массива получить массив в котором данные перемешаны случайным образом, т.е получается что из некоторого набора данных получается новый в котором элементы расположены на совершенно случаных позициях.
И вот так я приступил к созданию своей функции перестановки элемента в массиве случайным образом…
Итак, сначала мне пришло в голову сделать следующим образом: возьмем массив исходных данных, создадим пустой массив-аккумулятор; после чего, а далее в цикле (по всем элементам массива) будем создавать случайное число, которое будем интерпретировать как индекс элемента в исходном массиве. Далее вычленяем элемент с полученным индексом и помещаем его в массив-аккумулятор, после чего «сужаем исходный массив», удаляя из него тот самый элемент.
То есть, в итоге получаем нечто подобное (прошу прощения за корявый код, т.к набиралось в спешке и на моем смартфоне):
import std.random;
import std.stdio;
auto permutate(T)(T[] sourceArray)
{
T[] result;
auto generator = Random(unpredictableSeed);
foreach (i; 0..sourceArray.length)
{
size_t slicingIndex;
if (i <= 1)
{
slicingIndex = uniform(0, sourceArray.length - 1, generator);
}
else
{
slicingIndex = 0;
}
result ~= sourceArray[slicingIndex];
if (slicingIndex != sourceArray.length)
{
sourceArray = sourceArray[0..slicingIndex] ~ sourceArray[slicingIndex+1..$];
}
}
return result;
}
И тут я подумал, что так не пойдет...
На этом месте я решил попробовать поставить свой собственный эксперимент на правах своей же идеи. Дело в том, что мне показалось, что алгоритм приведенный выше не обладает особой элегантностью (хотя в будущем его можно "ранжифицировать") и что это, по своей сути, решение "в лоб". Это обстоятельство привело к тому, что я решил пойти иным путем, вместо выдергивания и накопления случайно выбранного элемента, попробовать использовать циркулярный буфер, выполняя случайный сдвиг.
Но, случайный сдвиг не перемешивает элементы, а лишь сдвигает существующие, не приводя к изменению их текущего положения. Осознав этот факт и предполагая, что в идее со сдвигом есть что-то ценное, я предположил, что эту концепцию надо расширить, сдвигая не весь массив, а только некий элемент выбранный случайным образом на случайную величину.
Поначалу, предполагалось, что можно будет с помощью циркулярного буфера, "вращать" массив вокруг некоторого случайного элемента, перезаписывая полученным таким образом массивом исходный. Однако, эта идея дала трещину, да и реализации циркулярного буфера у меня под рукой не было, несмотря на то, что нечто подобное описывалось в блоге, когда мы создавали свой тип массивов с произвольной индексацией.
Поэтому, я взялся за концепцию случайного сдвига произвольно выбранного элемента, для чего необходимо было реализовать функцию сдвига на произвольную величину любого элемента любого массива.
Проще всего в этой ситуации было поступить так, как делается в алгоритме для шифра Тритемиуса: дело в том, что там для определения позиции на которую сдвигается буква использовано прибавление величины сдвига к номеру (индексу) текущей шифруемой буквы; а чтобы не произошел выход за границы массива с алфавитом шифра, используется деление с остатком на количество букв символов в алфавите шифра (т.е на длину массива с алфавитом).
Именно этот подход позволяет создать необходимую функцию shiftNth (предполагаем, что сдвиг идет вправо и только на неотрицательную величину):
auto shiftNth(T)(T[] shifted, size_t index, size_t shift)
{
auto accumulator = shifted.dup;
auto newPosition = (index + shift) % shifted.length;
auto first = shifted[index];
auto second = shifted[newPosition];
accumulator[newPosition] = first;
accumulator[index] = second;
return accumulator;
}
Для того, чтобы осуществить такой "сдвиг" необходимо просто поменять местами некоторые элементы в исходном массиве, а чтобы это было безопасно, операцию производим над изменяемой копией массива. При этом, у нас получается некоторое подобие "вращения" массива в циркулярном буфере, поскольку лишь некоторые элементы при этой процедуре способны действительно поменяться местами.
Теперь, можно просто поменять таким образом несколько элементов в исходном массиве (сколько именно - не знаю), выполняя переприсваивание текущему массиву результата работы функции shiftNth со случайными параметрами индекса и сдвига. К сожалению, я не математик, и я не могу построить достаточно убедительного доказательства или произвести собственные расчеты оптимального количества операций shiftNth в алгоритме, поэтому я просто решил взять наиболее удобное значение, подобрав его эмпирически: количество операций случайного сдвига в моем варианте равно количеству элементов массива, деленному пополам.
Код реализации:
auto shiftPermutate(T)(T[] prearray)
{
auto generator = Random(unpredictableSeed);
foreach (i; 0..prearray.length / 2)
{
auto index = uniform(0, prearray.length - 1, generator);
auto shift = uniform(0, prearray.length, generator);
prearray = prearray.shiftNth(index, shift);
}
return prearray;
}
Испытать код можно к примеру таким образом:
void main()
{
int[] a = [1,2,3,4,5,6,7];
writeln(permutate([1,2,3,4,5]));
writeln(shiftNth(a, 3, 5));
writeln(shiftPermutate([1,2,3,4,5,6]));
writeln(shiftPermutate([1,2,3,4,5,6]));
}
Вот таким получилось мое скромное "открытие", на которое в общем я и не претендую. Я не уверен в том, что идеи, лежащие в основе алгоритма являются правильными, и что сам алгоритм оптимален, но иногда можно использовать и его, особенно, если пишешь под давлением времени и в своем распоряжении имеешь только смартфон с ldc и micro...
