Generando secuencias aleatorias predecibles: un enfoque diferente para la permutación

Una vez trabajé en un proyecto cuya tarea era crear una utilidad para el examen. Un usuario crea preguntas, las combina en una prueba, establece algunas reglas como el tiempo de ejecución, cómo contar puntos. Y el otro usuario simplemente abre y responde preguntas. Entre otras cosas, la tarea consistía en darse cuenta de la capacidad de mezclar la secuencia de preguntas, pero para que para un usuario en particular fuera lo mismo que cuando se abrió por primera vez.

La tarea es bastante simple y la resolvimos rápidamente. Y la solución fue la siguiente: tenemos n preguntas. Por combinatoria, sabemos que si tenemos n> 1 elementos, al reorganizar los elementos en lugares, podemos obtener diferentes secuencias de estos elementos, donde el número máximo de secuencias diferentes es$$$n!$. Entonces se decidió, escribimos que significa una función, calculamos el factorial allí, generamos la enésima secuencia y generamos el número n al azar y lo escribimos en la base de datos. Enviamos hrenak-hrenak y en producción a probadores. Y todo parece ser normal, pero si algo inesperado no hubiera sucedido, este artículo no hubiera sido así.

Que pasó

Y sucedió $$$21! = ‭51 090 942 171 709 440 000‬$. Mantener el valor factorial de números mayores que 20 (en realidad 13) fue un gran problema que no se tuvo en cuenta al escribir el código. Como resultado, si hubo más preguntas, entonces, por supuesto, nada funcionó. Era necesario resolver de alguna manera el defecto. Una opción era simplemente dividir la matriz, mezclar los elementos en las sub-matrices y luego mezclarlos nosotros mismos. Como tal, esta opción es aceptable, pero como todos me confiaron la solución, decidí ir por el otro lado.

Oh nueva forma maravillosa

, — « , ?». , . - 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, . - , . - . , , - , . , , ? .

, Java, java.util.Collections.shuffle() . Java .