Мое скромное «открытие»

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

И вот так я приступил к созданию своей функции перестановки элемента в массиве случайным образом…

Итак, сначала мне пришло в голову сделать следующим образом: возьмем массив исходных данных, создадим пустой массив-аккумулятор; после чего, а далее в цикле (по всем элементам массива) будем создавать случайное число, которое будем интерпретировать как индекс элемента в исходном массиве. Далее вычленяем элемент с полученным индексом и помещаем его в массив-аккумулятор, после чего «сужаем исходный массив», удаляя из него тот самый элемент.

То есть, в итоге получаем нечто подобное (прошу прощения за корявый код, т.к набиралось в спешке и на моем смартфоне):

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…

Добавить комментарий