Генерация предсказуемых случайных последовательностей: другой подход к пермутациям

Однажды я работал над проектом, задачей которого было создание утилиты для экзаменации. Один пользователь создает вопросы, объединяет их в тест, устанавливает какие-то правила типа времени на исполнение, как подсчитывать баллы. А другой пользователь просто открывает и отвечает на вопросы. Кроме прочего, стояла задача реализовать возможность перемешать последовательность вопросов, но так, чтобы для определенного пользователя она была такой же, как при первом открытии.

Задача довольно простая и решили её у нас быстро. А решение было следующим: У нас есть n вопросов. Из комбинаторики мы знаем, что если у нас есть n > 1 элементов, мы, переставляя элементы местами, можем получить разные последовательности этих элементов, где максимальное число отличающихся последовательностей равно

$n!$

. Вот и было решено, пишем значит функцию, посчитаем там факториал, сгенерируем n-ную последовательность, а само число n сгенерируем рандомно и запишем в БД. Хренак-хренак и в продакшен отправляем тестерам. И вроде бы все нормально, но ведь не случись что-то непредвиденное, этой статьи бы не было.

Что произошло

А произошло

$21! = ‭51 090 942 171 709 440 000‬$

. Хранить значение факториала чисел больше 20-и (на самом деле 13-и) стало большой проблемой, которую при написании кода не учли. В итоге если вопросов было больше, то разумеется ничего не работало. Нужно было как-то решать недоработку. Одним из вариантов было попросту поделить массив, перемешать элементы в под-массивах, а после перемешать их самих. Как таковой, этот вариант приемлем, но раз исправить все доверили мне, я решил пойти другим путем.

О новый дивный путь

Чтобы окончательно определиться с решением, я задался вопросом — «А что нам нужно, сгенерировать определенную последовательность для определенного пользователя или просто перемешать её с последующей возможностью повторения?». Так как требовалось именно второе, то я решил взглянуть на задачу и пермутации под другим углом. Ведь нужно было всего-то из n элементов создать случайную последовательность, а сами элементы в последовательности должны были встречаться единожды. Это означает, что случайным образом можно выбрать один из элементов, сделать его первым в последовательности, а следующий выбрать таким же случайным образом, но уже из оставшихся элементов. И так n раз, пока мы не соберем нашу новую последовательность.

Осталось реализовать идею и написать работающий код. Для начала нам понадобится массив, который мы хотим перемешать:

public static int[] generateArray(int n) { 	int[] array = new int[n];  	for (int i = 0; i < n; i++) { 		array[i] = i; 	}  	return array; } 

После нам нужно скопировать наш массив, разумеется если он нам понадобиться в исходном виде, что в Java делается очень просто:

int[] arrayCopy = Array.copyOf(mainArray, mainArray.length); 

Теперь мы готовы перемешать наш массив:

public static int[] shuffleArray(int[] array, Random rand) { 	int[] shuffledArray = new int[array.length];  	for (int i = 0; i < array.length; i++) { 		int origIndex = rand.nextInt(array.length - i); 		shuffledArray[i] = array[origIndex];  		int temp = array[origIndex]; 		array[origIndex] = array[array.length - i - 1]; 		array[array.length - i - 1] = temp; 	}  	return shuffledArray; } 

А чтобы все проверить, мы используем следующий код, где указываем seed для генератора псевдослучайных чисел. В таком случае наша последовательность всегда будет предсказуема, а само число мы можем взять любое, будь то номер сессии, текущее время или такое-же случайное число:

public static void main(String[] args) { 	int[] mainArray = generateArray(30); 	int[] arrayCopy = Arrays.copyOf(mainArray, mainArray.length);  	Random rand = new Random(419L); 	int[] shuffledArray = shuffleArray(arrayCopy, rand);  	for (int i = 0; i < shuffledArray.length; i++) { 		System.out.print(shuffledArray[i] + " "); 	}  	System.out.println(); } 

Собрав все воедино, мы получаем решение для моей задачи. Временная сложность данного способа

$O(n)$

и с генерацией случайной последовательности, которую легко будет повторить он справляется:

Полный код

import java.util.Random; import java.util.Arrays;  public class Shuffle { 	public static void main(String[] args) { 		int[] mainArray = generateArray(30); 		int[] arrayCopy = Arrays.copyOf(mainArray, mainArray.length);  		Random rand = new Random(419L); 		int[] shuffledArray = shuffleArray(arrayCopy, rand);  		for (int i = 0; i < shuffledArray.length; i++) { 			System.out.print(shuffledArray[i] + " "); 		}  		System.out.println(); 	}  	public static int[] generateArray(int n) { 		int[] array = new int[n];  		for (int i = 0; i < n; i++) { 			array[i] = i; 		}  		return array; 	}  	public static int[] shuffleArray(int[] array, Random rand) { 		int[] shuffledArray = new int[array.length];  		for (int i = 0; i < array.length; i++) { 			int origIndex = rand.nextInt(array.length - i); 			shuffledArray[i] = array[origIndex];  			int temp = array[origIndex]; 			array[origIndex] = array[array.length - i - 1]; 			array[array.length - i - 1] = temp; 		}  		return shuffledArray; 	} } 

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

public static int[] subArrayElem(int nth, int elemNumber) { 	int[] sequence = new int[elemNumber];  	for (int i = 1; i <= elemNumber; i++) { 		sequence[elemNumber - i] = nth % i; 		nth /= i; 	}  	return sequence; } 

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

public static int[] shuffleArray(int[] array, int nth) { 	int[] shuffledArray = new int[array.length]; 	int[] sequence = subArrayElem(nth, array.length);  	for (int i = 0; i < array.length; i++) { 		int origIndex = sequence[i]; 		shuffledArray[i] = array[origIndex]; 		shiftArray(array, origIndex); 	}  	return shuffledArray; }  public static void shiftArray(int[] array, int index) { 	for (int i = index; i < array.length - 1; i++) { 		array[i] = array[i + 1]; 	} } 

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

Заключение

Под конец хочется сказать, что есть способы улучшить алгоритм. Можно использовать BigInteger, в таком случае вообще можно не переживать насчет больших значений факториала. Также возможно кому-то покажется, что задача тривиальна и ей не нужна отдельная статья. Возможно кому-то она действительно пригодится. Но самое главное, перед тем, как реализовывать что-либо подумайте, а действительно ли вы понимаете задачу. Может быть ваше идеальное, но сложное решение не является необходимым, а решить вашу проблему можно намного проще? В описанном мной случае именно так все и было.

UPD:

Когда все это писалось для проекта, писалось не на Java, там не было встроенной возможности типа java.util.Collections.shuffle() с объектом рандома. А щас написал на Java потому что мне нравится на ней писать алгоритмы. Думаю стоит это уточнить

FavoriteLoadingДобавить в избранное
Posted in Без рубрики

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *