خوارزمية Fisher-Yates لإعادة الترتيب عشوائيًا

تنتج خوارزمية Fisher-Yates ترتيبًا عشوائيًا لتسلسل معين. وضعت هذه الخوارزمية سنة 1938 من قبل Ronald Fisher و Frank Yates.

خوارزمية Fisher-Yates الأصلية

خطوات الخوارزمية

تتبع خوارزمية Fisher-Yates الأصلية الخطوات التالية:

1. تختار الخوارزمية بطريقة عشوائية أحد العناصر التي لم يتغير موقعها ضمن المصفوفة المعطاة.
2. تضع الخوارزمية العنصر المختار في الخطوة السابقة في بداية (أو نهاية) مصفوفة جديدة.
3. تحذف الخوارزمية العنصر المختار من المصفوفة الأصلية.
4. تعاد الخطوات 2 و 3 إلى أن تصبح المصفوفة الأصلية فارغة.

مثال:

لنفترض أننا نرغب في إعادة ترتيب عناصر المصفوفة: {arr[] = {1, 2, 3, 4, 5:

{1, 2, 3, 4, 5} => {1, 2, 3, 5} and {4}

{1, 2, 3, 5} => {2, 3, 5} and {4, 1}

{2, 3, 5} => {2, 5} and {4, 1, 3}

{2, 5} => {2} and {4, 1, 3, 5}

{2} => {} and {4, 1, 3, 5, 2}

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

• بايثون:

import random

def shuffle(arr, n):
    # قائمة جديدة
    shuffled_arr = []
    for i in range(n - 1, 0, -1):
        # توليد رقم عشوائي بين 0 وطول المصفوفة
        j = random.randint(0, i)
        # إضافة العنصر المختار من المصفوفة الأصلية إلى المصفوفة الجديدة
        shuffled_arr.append(arr[j])
        
        # حذف العنصر المختار من المصفوفة الأصلية
        arr.pop(j)
    return shuffled_arr

if __name__ == '__main__':
    arr = list(range(10))
    n = len(arr)
    print(shuffle(arr, n))

• جافا:

التعقيد الزمني

يبلغ التعقيد الزمني لهذه الخوارزمية المقدار O(n^2)‎.

خوارزمية Drustenfeld-Knuth

تعد خوارزمية Drustenfeld-Knuth نسخة أحدث من Fisher-Yates وقد وضعت سنة 1964، وتختلف هذه الخوارزمية عن نسختها القديمة اختلافًا بسيطًا ولكنّه مهم في نفس الوقت. إذ تبدل هذه الخوارزمية بين موقع العنصر المختار عشوائيًا وموقع آخر عنصر في المصفوفة لم يجر اختياره من قبل الخوارزمية بعد. إلى جانب أنّ هذه الخوارزمية لا تستخدم مصفوفة إضافية بل تعيد ترتيب المصفوفة نفسها، الأمر الذي يوفّر الكثير من المساحة إن كانت المدخلات كبيرة جدًّا.

خطوات الخوارزمية

تتبع خوارزمية Drustenfeld-Knuth الخطوات التالية:

1. تختار الخوارزمية بطريقة عشوائية أحد العناصر التي لم يتغير موقعها ضمن المصفوفة المعطاة.
2. تبدل الخوارزمية بين موقع العنصر المنتخب وموقع آخر عنصر في المصفوفة لم يجر اختياره من قبل الخوارزمية بعد.
3. تعاد الخطوة 2 إلى أن لا يبقى أيّ عنصر في مكانه الأصلي.

مثال:

{ A, B, C, D, E, F, G, H } => { A, B, C, H, E, F, G, D }

{ A, B, C, H, E, F, G, D } => { A, B, C, H, G, F, E, D }

{ A, B, C, H, G, F, E, D } => { A, F, C, H, E, B, E, D }

{ A, F, C, H, G, B, E, D } => { A, F, C, G, H, B, E, D }

{ A, F, C, G, H, B, E, D } => { G, F, C, A, H, B, E, D }

{ G, F, C, A, H, B, E, D } => { G, C, F, A, H, B, E, D }

{ G, C, F, A, H, B, E, D } => { C, G, F, A, H, B, E, D }

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

#include<bits/stdc++.h> 
#include <stdlib.h> 
#include <time.h> 
using namespace std; 

// دالة مساعدة للتبديل بين الأعداد الصحيحة 
void swap (int *a, int *b) 
{ 
	int temp = *a; 
	*a = *b; 
	*b = temp; 
} 

// دالة مساعدة لطباعة عناصر المصفوفة
void printArray (int arr[], int n) 
{ 
	for (int i = 0; i < n; i++) 
		cout << arr[i] << " "; 
	cout << "\n"; 
} 

// ترتب الدالة عناصر المصفوفة المعطاة ترتيبًا عشوائيًا
void randomize (int arr[], int n) 
{ 
	// لضمان عدم الحصول على نفس النتيجة عند تنفيذ الشيفرة
	srand (time(NULL)); 

	// البدء من آخر عنصر في المصفوفة والتبديل بين العناصر
	// i > 0 لا حاجة للوصول إلى العنصر الأول لذا تستخدم الشيفرة التعبير
	for (int i = n - 1; i > 0; i--) 
	{ 
		// اختيار موقع عشوائي من 0 إلى i 
		int j = rand() % (i + 1); 

		// التبديل بين موقعي العنصر الحالي والموقع العشوائي
		// المحسوب في الخطوة السابقة
		swap(&arr[i], &arr[j]); 
	} 
} 

// اختبار الدوال السابقة
int main() 
{ 
	int arr[] = {1, 2, 3, 4, 5, 6, 7, 8}; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	randomize (arr, n); 
	printArray(arr, n); 

	return 0; 
}

• بايثون:

import random 

// 
# ترتب الدالة عناصر المصفوفة المعطاة ترتيبًا عشوائيًا
def randomize (arr, n): 

	# البدء من آخر عنصر في المصفوفة والتبديل بين العناصر
	# i > 0 لا حاجة للوصول إلى العنصر الأول لذا تستخدم الشيفرة التعبير
	for i in range(n-1,0,-1): 
		# اختيار موقع عشوائي بين 0 و i
		j = random.randint(0,i+1) 

		# التبديل بين موقعي العنصر الحالي والموقع العشوائي
		# المحسوب في الخطوة السابقة 
	return arr 

# اختبار الدالة السابقة
arr = [1, 2, 3, 4, 5, 6, 7, 8] 
n = len(arr) 
print(randomize(arr, n))

• جافا:

import java.util.Random; 
import java.util.Arrays; 
public class ShuffleRand 
{ 
	// ترتب الدالة عناصر المصفوفة المعطاة ترتيبًا عشوائيًا 
	static void randomize( int arr[], int n) 
	{ 
		// إنشاء كائن للصنف Random
		Random r = new Random(); 
		
		
		// البدء من آخر عنصر في المصفوفة والتبديل بين العناصر
		// i > 0 لا حاجة للوصول إلى العنصر الأول لذا تستخدم الشيفرة التعبير
		for (int i = n-1; i > 0; i--) { 
			
			// اختيار موقع عشوائي بين 0 و i
			int j = r.nextInt(i+1); 
			
			// التبديل بين موقعي العنصر الحالي والموقع العشوائي
			// المحسوب في الخطوة السابقة
			int temp = arr[i]; 
			arr[i] = arr[j]; 
			arr[j] = temp; 
		} 
		// طباعة المصفوفة بعد إعادة ترتيبها عشوائيًا
		System.out.println(Arrays.toString(arr)); 
	} 
	
	// اختبار التابع السابق
	public static void main(String[] args) 
	{ 
		
		int[] arr = {1, 2, 3, 4, 5, 6, 7, 8}; 
		int n = arr.length; 
		randomize (arr, n); 
	} 
}

التعقيد الزمني

يبلغ التعقيد الزمني لخوارزمية Drustenfeld-Knuth المقدار O(n)‎.

مصادر

• صفحة Shuffle a given array using Fisher–Yates shuffle Algorithm في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Fisher–Yates shuffle في موقع Wikipedia.
• صفحة Understanding the Fisher-Yates Shuffling Algorithm في موقع Exception Not Found.