Gerando seqüências aleatórias previsíveis: uma abordagem diferente da permutação

Uma vez, trabalhei em um projeto cuja tarefa era criar um utilitário para o exame. Um usuário cria perguntas, combina-as em um teste, estabelece algumas regras como tempo de execução, como contar pontos. E o outro usuário simplesmente abre e responde a perguntas. Entre outras coisas, a tarefa era perceber a capacidade de misturar a sequência de perguntas, mas para que um usuário em particular fosse o mesmo de quando foi aberto pela primeira vez.

A tarefa é bastante simples e a resolvemos rapidamente. E a solução foi a seguinte: Temos n perguntas. A partir da combinatória, sabemos que, se tivermos n> 1 elementos, reorganizando os elementos em alguns lugares, podemos obter diferentes seqüências desses elementos, onde o número máximo de seqüências diferentes é$$$n!$. Assim, foi decidido que escrevemos significa uma função, calculamos o fatorial ali, geramos a enésima sequência e geramos o próprio número n aleatoriamente e o escrevemos no banco de dados. Enviamos hrenak-hrenak e em produção para testadores. E tudo parece estar normal, mas se algo inesperado não tivesse acontecido, este artigo não teria sido.

O que aconteceu

E aconteceu $$$21! = ‭51 090 942 171 709 440 000‬$. Manter o valor fatorial de números maior que 20 (na verdade, 13) foi um grande problema que não foi levado em consideração ao escrever o código. Como resultado, se houver mais perguntas, é claro que nada funcionou. Era necessário resolver de alguma forma a falha. Uma opção era simplesmente dividir a matriz, misturar os elementos nas sub-matrizes e depois misturá-los nós mesmos. Como tal, essa opção é aceitável, mas como todos me confiaram a correção, decidi seguir o outro caminho.

Oh novo caminho maravilhoso

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