Однажды я работал над проектом, задачей которого было создание утилиты для экзаменации. Один пользователь создает вопросы, объединяет их в тест, устанавливает какие-то правила типа времени на исполнение, как подсчитывать баллы. А другой пользователь просто открывает и отвечает на вопросы. Кроме прочего, стояла задача реализовать возможность перемешать последовательность вопросов, но так, чтобы для определенного пользователя она была такой же, как при первом открытии.
Задача довольно простая и решили её у нас быстро. А решение было следующим: У нас есть n вопросов. Из комбинаторики мы знаем, что если у нас есть n > 1 элементов, мы, переставляя элементы местами, можем получить разные последовательности этих элементов, где максимальное число отличающихся последовательностей равно 
. Вот и было решено, пишем значит функцию, посчитаем там факториал, сгенерируем n-ную последовательность, а само число n сгенерируем рандомно и запишем в БД. Хренак-хренак и в продакшен отправляем тестерам. И вроде бы все нормально, но ведь не случись что-то непредвиденное, этой статьи бы не было.
Что произошло
А произошло 
. Хранить значение факториала чисел больше 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();
}
Собрав все воедино, мы получаем решение для моей задачи. Временная сложность данного способа 
и с генерацией случайной последовательности, которую легко будет повторить он справляется:
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 потому что мне нравится на ней писать алгоритмы. Думаю стоит это уточнить
