Menghasilkan urutan acak yang dapat diprediksi: pendekatan permutasi yang berbeda

Suatu hari saya mengerjakan sebuah proyek yang tugasnya adalah menciptakan utilitas untuk ujian. Satu pengguna membuat pertanyaan, menggabungkannya ke dalam tes, menetapkan beberapa aturan seperti waktu eksekusi, cara menghitung poin. Dan pengguna lain hanya membuka dan menjawab pertanyaan. Antara lain, tugasnya adalah menyadari kemampuan untuk mencampur urutan pertanyaan, tetapi agar bagi pengguna tertentu itu akan sama seperti ketika pertama kali dibuka.

Tugasnya cukup sederhana dan kami menyelesaikannya dengan cepat. Dan solusinya adalah sebagai berikut: Kami punya pertanyaan. Dari kombinatorik, kita tahu bahwa jika kita memiliki n> 1 elemen, dengan mengatur ulang elemen di tempat, kita bisa mendapatkan urutan berbeda dari elemen-elemen ini, di mana jumlah maksimum dari urutan yang berbeda adalah$$$n!$. Jadi diputuskan, kita menulis artinya fungsi, kita menghitung faktorial di sana, menghasilkan urutan ke-n, dan menghasilkan nomor n itu sendiri secara acak dan menulisnya ke database. Kami mengirim hrenak-hrenak dandiproduksiuntuk penguji. Dan semuanya tampak normal, tetapi jika sesuatu yang tidak terduga tidak terjadi, artikel ini tidak akan terjadi.

Apa yang terjadi

Dan terjadi $$$21! = ‭51 090 942 171 709 440 000‬$. Menjaga nilai faktorial angka lebih besar dari 20 (sebenarnya 13) adalah masalah besar yang tidak diperhitungkan saat menulis kode. Akibatnya, jika ada lebih banyak pertanyaan, maka tentu saja tidak ada yang berhasil. Itu perlu untuk entah bagaimana menyelesaikan cacat. Salah satu opsi adalah dengan membagi array, mencampur elemen-elemen dalam sub-array, dan kemudian mencampurnya sendiri. Dengan demikian, opsi ini dapat diterima, tetapi karena semua orang mempercayakan saya pada perbaikannya, saya memutuskan untuk memilih jalan lain.

Oh cara baru yang luar biasa

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