Get best of the week

生成可预测的随机序列：一种不同的置换方法

有一次我从事一个项目，该项目的任务是创建考试实用程序。一个用户创建问题，将其合并到测试中，建立一些规则，例如执行时间，如何计算分数。而另一个用户只是打开并回答问题。除其他事项外，任务是实现混合问题序列的能力，但对于特定用户而言，该功能与首次打开时的功能相同。


任务很简单，我们很快就解决了。解决方案如下：我们有n个问题。从组合函数中我们知道，如果我们有n> 1个元素，则通过将元素重新排列在位置上，我们可以获得这些元素的不同序列，其中最大不同序列数为n!。因此决定，我们将其编写为一个函数，然后在其中计算阶乘，生成第n个序列，并随机生成数字n并将其写入数据库。我们将hrenak-hrenak和生产中的产品发送给测试人员。一切似乎都很正常，但是如果没有发生意外，这篇文章就不会出现。


发生了什么


发生了 21!=‭51090942171709440000‬。保持数字的阶乘值大于20（实际上是13）是一个很大的问题，编写代码时没有考虑到。结果，如果还有更多问题，那么当然没有任何作用。必须以某种方式解决该缺陷。一种选择是简单地划分数组，混合子数组中的元素，然后自己混合它们。因此，此选项是可以接受的，但是由于每个人都将修复程序托付给我，因此我决定采用其他方法。


哦，新奇妙的方式


为了最终决定解决方案，我问了自己一个问题：“我们需要什么，为特定用户生成特定序列，或者将其与后续重复的可能性混合在一起？” 由于这是必需的第二个，因此我决定从另一个角度来看问题和排列。毕竟，必须从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, . - , . - . , , - , . , , ? .



UPD:

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

More articles:


All Articles