Générer des séquences aléatoires prévisibles: une approche différente de la permutation

Une fois, j'ai travaillé sur un projet dont la tâche était de créer un utilitaire pour l'examen. Un utilisateur crée des questions, les combine dans un test, établit des règles telles que le temps d'exécution, comment compter les points. Et l'autre utilisateur ouvre simplement et répond aux questions. Entre autres choses, la tâche consistait à réaliser la capacité de mélanger la séquence de questions, mais de sorte que pour un utilisateur particulier, ce serait la même que lors de son ouverture.

La tâche est assez simple et nous l'avons résolue rapidement. Et la solution était la suivante: nous avons n questions. De la combinatoire, nous savons que si nous avons n> 1 éléments, en réorganisant les éléments par endroits, nous pouvons obtenir différentes séquences de ces éléments, où le nombre maximum de séquences différentes est$$$n!$. Il a donc été décidé, nous écrivons cela signifie une fonction, nous y calculons la factorielle, générons la nième séquence, générons le nombre n lui-même au hasard et l'écrivons dans la base de données. Nous envoyons des hrenak-hrenak et en production aux testeurs. Et tout semble normal, mais si quelque chose d'inattendu ne s'était pas produit, cet article ne l'aurait pas été.

Qu'est-il arrivé

Et c'est arrivé $$$21! = ‭51 090 942 171 709 440 000‬$. Garder la valeur factorielle des nombres supérieurs à 20 (en fait 13) était un gros problème qui n'a pas été pris en compte lors de l'écriture du code. En conséquence, s'il y avait plus de questions, alors bien sûr, rien ne fonctionnait. Il était nécessaire de résoudre en quelque sorte la faille. Une option était simplement de diviser le tableau, de mélanger les éléments dans les sous-tableaux, puis de les mélanger nous-mêmes. En tant que telle, cette option est acceptable, mais comme tout le monde m'a confié le correctif, j'ai décidé d'aller dans l'autre sens.

Oh nouvelle façon merveilleuse

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