توليد تسلسلات عشوائية يمكن التنبؤ بها: نهج مختلف للتبديل

بمجرد أن عملت على مشروع مهمته كانت إنشاء أداة للفحص. يقوم أحد المستخدمين بإنشاء أسئلة ، ودمجها في اختبار ، ووضع بعض القواعد مثل وقت التنفيذ ، وكيفية حساب النقاط. والمستخدم الآخر يفتح ببساطة ويجيب عن الأسئلة. من بين أمور أخرى ، كانت المهمة هي إدراك القدرة على مزج تسلسل الأسئلة ، ولكن حتى بالنسبة لمستخدم معين ، سيكون الأمر كما هو عند فتحه لأول مرة.

المهمة بسيطة للغاية وقمنا بحلها بسرعة. وكان الحل كما يلي: لدينا عدد من الأسئلة. من التوافقيات ، نعلم أنه إذا كان لدينا عناصر n> 1 ، من خلال إعادة ترتيب العناصر في الأماكن ، فيمكننا الحصول على تسلسلات مختلفة من هذه العناصر ، حيث يكون الحد الأقصى لعدد التسلسلات المختلفة$$$n!$. لذلك تقرر ، نكتبها تعني دالة ، نحسب العامل هناك ، نولد التسلسل nth ، وننشئ الرقم n نفسه بشكل عشوائي ونكتبه في قاعدة البيانات. نرسل hrenak-hrenak وفيالإنتاجإلى المختبرين. ويبدو أن كل شيء طبيعي ، ولكن إذا لم يحدث شيء غير متوقع ، لما كانت هذه المقالة.

ماذا حدث

وحدث $$$21! = ‭51 090 942 171 709 440 000‬$. كان الحفاظ على القيمة العددية للأرقام أكبر من 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, . - , . - . , , - , . , , ? .

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