Generieren vorhersagbarer Zufallssequenzen: ein anderer Ansatz zur Permutation

Einmal arbeitete ich an einem Projekt, dessen Aufgabe es war, ein Dienstprogramm für die Prüfung zu erstellen. Ein Benutzer erstellt Fragen, kombiniert sie zu einem Test und legt einige Regeln fest, z. B. die Ausführungszeit und das Zählen von Punkten. Und der andere Benutzer öffnet und beantwortet einfach Fragen. Unter anderem bestand die Aufgabe darin, die Fähigkeit zu realisieren, die Reihenfolge der Fragen zu mischen, aber für einen bestimmten Benutzer wäre es das gleiche wie beim ersten Öffnen.

Die Aufgabe ist recht einfach und wir haben sie schnell gelöst. Und die Lösung war wie folgt: Wir haben n Fragen. Aus der Kombinatorik wissen wir, dass wir, wenn wir n> 1 Elemente haben, durch Umordnen der Elemente an bestimmten Stellen verschiedene Sequenzen dieser Elemente erhalten können, wobei die maximale Anzahl verschiedener Sequenzen ist$$$n!$. Also wurde entschieden, wir schreiben es bedeutet eine Funktion, wir berechnen dort die Fakultät, erzeugen die n-te Folge und erzeugen die Zahl n selbst zufällig und schreiben sie in die Datenbank. Wir senden Hrenak-Hrenak und in Produktion an Tester. Und alles scheint normal zu sein, aber wenn nicht etwas Unerwartetes passiert wäre, wäre dieser Artikel nicht gewesen.

Was ist passiert

Und ist passiert $$$21! = ‭51 090 942 171 709 440 000‬$. Das Beibehalten des Fakultätswerts von Zahlen größer als 20 (tatsächlich 13) war ein großes Problem, das beim Schreiben des Codes nicht berücksichtigt wurde. Wenn es also mehr Fragen gab, funktionierte natürlich nichts. Es war notwendig, den Fehler irgendwie zu lösen. Eine Möglichkeit bestand darin, das Array einfach zu teilen, die Elemente in den Unterarrays zu mischen und sie dann selbst zu mischen. Daher ist diese Option akzeptabel, aber da mir alle das Update anvertraut haben, habe ich mich für den anderen Weg entschieden.

Oh neuer wunderbarer Weg

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