ما هي خوارزمية فيشر-ييتس للخلط العشوائي (Fisher-Yates Shuffle Algorithm)؟

عندما تحتاج إلى ترتيب الطلاب عشوائيًا أو تكوين مجموعات عادلة أو اختيار اسم من قائمة، فإن الخوارزمية المسؤولة عن العشوائية تصبح حاسمة. خوارزمية فيشر-ييتس (Fisher-Yates Shuffle Algorithm) هي الطريقة القياسية والأكثر عدالة لتوليد ترتيب عشوائي لعناصر أي قائمة. سواء كنت معلمًا يستخدم أداة إنشاء المجموعات العشوائية أو مطورًا يبني نظام اقتراع، فإن فهم هذه الخوارزمية يضمن لك نزاهة العملية.

ما هي خوارزمية فيشر-ييتس للخلط العشوائي؟

خوارزمية فيشر-ييتس هي طريقة خوارزمية لتوليد تبديل عشوائي (random permutation) لمجموعة محدودة من العناصر. ببساطة، تقوم بأخذ قائمة العناصر المُراد خلطها، ثم تعمل من النهاية إلى البداية (أو العكس) وتختار عنصرًا عشوائيًا من العناصر المتبقية لتبديله مع العنصر الحالي. تضمن هذه الطريقة أن كل تبديل ممكن له نفس الاحتمالية بالضبط، مما يجعلها مثالية لأي تطبيق يتطلب عدالة إحصائية.

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

كيف تعمل خوارزمية فيشر-ييتس؟

النسخة الحديثة (Durstenfeld/Knuth) تعمل في تعقيد زمني O(n)، مما يعني أنها تتعامل بكفاءة مع القوائم الكبيرة. إليك الخطوات بالتفصيل مع مثال عملي:

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

1. ابدأ بمصفوفة (قائمة) تحتوي على جميع العناصر.

مثلاً، لدينا مصفوفة بأسماء طلاب: ["أحمد", "سارة", "عمر", "ليلى", "يوسف"].
الحجم الكلي n = 5.

1. مرر على المصفوفة من النهاية إلى البداية، بمؤشر i يبدأ من n-1 وينزل حتى 1.

في المرة الأولى i = 4 (آخر عنصر، يوسف).

1. اختر رقمًا عشوائيًا j بين 0 و i (شاملًا).

افترض أن j = 2 (أي العنصر في الموضع 2 وهو "عمر").

1. بدّل العنصر في الموضع i مع العنصر في الموضع j.

الآن تصبح المصفوفة: ["أحمد", "سارة", "يوسف", "ليلى", "عمر"].

1. قلل i بمقدار 1 وكرر الخطوات 3-4.

i = 3: اختر j عشوائيًا بين 0 و3، مثلاً j = 0 (أحمد). بدّل: ["ليلى", "سارة", "يوسف", "أحمد", "عمر"].

1. استمر حتى تصل إلى i = 1، ثم تتوقف.

بعد الجولة الأخيرة تكون المصفوفة مرتبة بترتيب عشوائي تمامًا، وكل ترتيب ممكن ظهر بنفس الاحتمال.

السر في عدالة الخوارزمية: عندما تختار j من نطاق 0 إلى i، فأنت تختار بالتساوي بين جميع العناصر التي لم تُثبّت بعد في موقعها النهائي. بما أن احتمال اختيار أي عنصر في كل خطوة متساوٍ، فإن الإجمالي يعطي توزيعًا منتظمًا لكل التبديلات.

لماذا نستخدم خوارزمية فيشر-ييتس في أداة إنشاء المجموعات العشوائية؟

في أدواتنا مثل أداة إنشاء المجموعات العشوائية وأداة اختيار الطالب العشوائي، تعتبر العدالة أمرًا بالغ الأهمية. يجب أن يكون لكل طالب فرصة متساوية للظهور في أي مجموعة، ولا يجب أن تتأثر النتائج بترتيب الإدخال أو بخوارزميات غير عادلة.

بعض الطرق البسيطة مثل ترتيب العناصر عشوائيًا باستخدام دالة المقارنة (sort with random comparator) قد تكون متحيزة وتعطي احتمالات غير متساوية. على سبيل المثال، دالة Math.random() - 0.5 في جافا سكريبت لا تضمن توزيعًا متساويًا، وقد تعطي بعض التبديلات فرصة أكبر من غيرها. لذلك نعتمد على خوارزمية فيشر-ييتس لضمان:

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

مقارنة مع طرق أخرى للخلط العشوائي

طريقة | العدالة | الكفاءة (n عنصر) | تعقيد الفهم
--- | --- | --- | ---
فرز عشوائي (Random Sort) | منحازة في معظم الحالات | O(n log n) | بسيطة لكن غير آمنة
اختيار عشوائي مع إزالة (Splice Random) | عادلة لكن بطيئة | O(n²) بسبب الإزاحة | واضحة
خوارزمية فيشر-ييتس | عادلة تمامًا | O(n) | بسيطة وسهلة التطبيق

يتضح من الجدول أن خوارزمية فيشر-ييتس تقدم أفضل توازن بين العدالة والسرعة. في السيناريوهات التعليمية حيث يتم استخدام أداة توليد الأزواج العشوائية، لا مجال للتحيز حتى لا يشعر الطلاب بأن التقسيم غير عادل.

تطبيق عملي بسيط (للإيضاح)

بالنسبة للمطورين الذين يبنون أدوات مشابهة أو يرغبون في تجربة الخوارزمية، إليك مثال بلغة JavaScript:

function shuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [array[i], array[j]] = [array[j], array[i]];
  }
  return array;
}

// استخدامها مع قائمة أسماء
const names = ["أحمد", "سارة", "عمر", "ليلى", "يوسف"];
console.log(shuffle(names)); // ترتيب عشوائي مثلاً: ["عمر", "ليلى", "أحمد", "يوسف", "سارة"]

هذا الكود ينفذ الخوارزمية بشكل دقيق. لاحظ أن Math.random() يولد عددًا عشوائيًا بين 0 و1، وعند ضربه في (i+1) ثم تقريبه للأسفل نحصل على رقم صحيح من 0 إلى i.

أسئلة شائعة حول خوارزمية فيشر-ييتس

هل يمكن أن تتكرر العناصر بعد الخلط؟

لا، الخوارزمية تقوم بتبديل العناصر في مواضعها فقط دون تكرار أي عنصر، فهي تنشئ تبديلًا (permutation) للقائمة الأصلية.

هل تحتاج الخوارزمية إلى مكتبات خاصة؟

لا، يمكن تنفيذها بسهولة باستخدام دوال أساسية مثل Math.random() ولا تحتاج إلى مكتبات خارجية. ولهذا فهي مناسبة جدًا للأدوات التعليمية المضمنة في صفحات الويب.

كيف تضمن الخوارزمية عدم التحيز؟

لأن كل عنصر يتم اختياره عشوائيًا من بين العناصر المتبقية غير المثبتة، وكل عنصر لديه نفس فرصة الاختيار في كل خطوة. رياضياً، احتمال إنتاج أي ترتيب معين هو 1/n! (واحد على مضروب عدد العناصر).

ماذا لو أردت اختيار عينة عشوائية دون خلط الكل؟

الخوارزمية قابلة للتعديل لاختيار عينة عشوائية بحجم k عبر إيقاف التكرار بعد k خطوات بدلاً من n-1. وهذا ما تستخدمه أداة اختيار الطالب العشوائي عند انتقاء اسم واحد فقط.

هل الأرقام العشوائية في المتصفح آمنة لتطبيقات حساسة؟

في السياقات التي تتطلب أمانًا عاليًا (مثل السحوبات المالية) يُفضل استخدام crypto.getRandomValues() بدلاً من Math.random()، لكن لاستخدامات التقسيم التعليمي كافٍ تمامًا.

خلاصة

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