Очень давно я думаю над одной задачей, часть решения которой, содержит функцию своеобразного перемешивания некоторого массива данных. Суть перемешивания довольно проста: нужно из исходного массива получить массив в котором данные перемешаны случайным образом, т.е получается что из некоторого набора данных получается новый в котором элементы расположены на совершенно случаных позициях.
И вот так я приступил к созданию своей функции перестановки элемента в массиве случайным образом…
Итак, сначала мне пришло в голову сделать следующим образом: возьмем массив исходных данных, создадим пустой массив-аккумулятор; после чего, а далее в цикле (по всем элементам массива) будем создавать случайное число, которое будем интерпретировать как индекс элемента в исходном массиве. Далее вычленяем элемент с полученным индексом и помещаем его в массив-аккумулятор, после чего «сужаем исходный массив», удаляя из него тот самый элемент.
То есть, в итоге получаем нечто подобное (прошу прощения за корявый код, т.к набиралось в спешке и на моем смартфоне):
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...