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


Задача довольно простая и решили её у нас быстро. А решение было следующим: У нас есть 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 потому что мне нравится на ней писать алгоритмы. Думаю стоит это уточнить