رياضيات الخلط العادل

يطرح الخلط سؤالاً رياضياً دقيقاً: إذا كان لدينا n عنصر مختلف، أنتج واحداً من !n ترتيب ممكن، بحيث يكون لكل ترتيب احتمال متساوٍ. بالنسبة لـ 12 عدد صحيح، يعني ذلك 479,001,600 تبديل. تم اختيار التسلسل أعلاه من تلك المجموعة باحتمال منتظم، وتم توليده بالكامل داخل متصفحك باستخدام خوارزمية فيشر-ييتس وواجهة Web Cryptography API.

فيشر-ييتس: الخوارزمية الحاسمة

وصف رونالد فيشر وفرانك ييتس طريقة الخلط الأصلية في كتابهما الصادر عام 1938 بعنوان Statistical Tables for Biological, Agricultural and Medical Research. قام دونالد كنوث لاحقاً بتحسينها للتنفيذ الحاسوبي في كتابه The Art of Computer Programming عام 1969. تسير النسخة الحديثة عبر المصفوفة بترتيب عكسي. في كل موضع، تختار عنصراً عشوائياً من الجزء غير المخلوط المتبقي وتبادل بينهما. تمرير واحد عبر البيانات ينتج خلطاً منتظماً مثالياً بزمن O(n) باستخدام مساحة إضافية O(1).

يُظهر برهان الصحة أنه بعد معالجة الموضع k، يكون كل ترتيب فرعي من بين !k ترتيب ممكن للعناصر الأولى k متساوي الاحتمال. بالاستقراء، تغطي النتيجة النهائية جميع تباديل !n باحتمال منتظم. خطأ شائع في التنفيذ، يُعرف بـ "الخلط الساذج"، يختار من المصفوفة بأكملها في كل خطوة بدلاً من الجزء غير المعالج. ينتج عن ذلك nⁿ تسلسل تبديل يُعيَّن على !n تبديل. بما أن nⁿ غير قابل للقسمة عموماً على !n، تصبح بعض التباديل أكثر احتمالاً من غيرها. تتجنب خوارزمية فيشر-ييتس هذا الأمر تماماً.

الحجم المذهل للتباديل

يتفوق النمو العاملي على كل دالة رياضية شائعة أخرى. عشرة عناصر تنتج 3,628,800 ترتيب. عشرون عنصراً تنتج أكثر من 2.4 كوينتليون. مجموعة أوراق لعب قياسية من 52 ورقة تولّد ما يقارب 8.07 \xC3\x97 10\xE2\x81\xB6\xE2\x81\xB7 ترتيب ممكن. هذا الرقم يتجاوز العدد المقدّر للذرات في الكون المرصود.

تأمّل: لو أن كل ذرة في الكون خلطت مجموعة أوراق مرة كل نانوثانية، وظلت تفعل ذلك منذ الانفجار العظيم قبل 13.8 مليار سنة، لكان إجمالي عمليات الخلط المنجزة لا يزال جزءاً ضئيلاً للغاية من !52. كل عملية خلط تقوم بها على هذه الصفحة تنشئ على الأرجح ترتيباً لم يوجد من قبل ولن يوجد مرة أخرى.

النقاط الثابتة: مفارقة الاضطراب

النقطة الثابتة هي رقم ينتهي به المطاف في موضعه الأصلي بعد الخلط. راقب الدوائر ذات الحلقات الذهبية أعلاه: تلك هي نقاطك الثابتة. العدد المتوقع للنقاط الثابتة هو 1 بالضبط، بغض النظر عن عدد العناصر التي تخلطها. عشرة عناصر، نقطة ثابتة متوقعة واحدة. عشرة آلاف عنصر، لا تزال واحدة.

احتمال بقاء عنصر معين في مكانه هو 1/n. بجمع ذلك على n عنصر، يساوي العدد المتوقع 1. هذه النتيجة، المرتبطة بالمفهوم الرياضي لـالاضطرابات الذي درسه ليونهارد أويلر، تعني أن نحو 36.8% من جميع عمليات الخلط ليس بها نقاط ثابتة، و36.8% بها نقطة واحدة بالضبط، و18.4% بها نقطتان بالضبط، وتنخفض الاحتمالات بسرعة بعد ذلك.

نظرية السبع خلطات

أثبت بيرسي دياكونيس وديف باير في عام 1992 أن خلط التقسيم القياسي لمجموعة من 52 ورقة يتطلب سبع تكرارات بالضبط للوصول إلى عشوائية كافية. يحقق خلط فيشر-ييتس الرقمي ما تقاربه سبع عمليات خلط تقسيم فعلية: عشوائية منتظمة مثالية في تمريرة حسابية واحدة.

في الفصل الدراسي

اطلب من كل طالب زيارة /sequence/1/10 والخلط مرة واحدة. ثم اسأل: هل حصل أي طالبين على نفس الترتيب؟ مع 3,628,800 ترتيب ممكن، التطابق أمر مستبعد للغاية. لعرض على جهاز العرض، افتح /sequence/1/52 وأجرِ الخلط بشكل متكرر. تتناثر الحلقات الملونة في أنماط جديدة في كل مرة، مما يجعل العشوائية مرئية فوراً. لا تتطلب الأداة حسابات، ولا تضع ملفات تعريف ارتباط، ولا تخزّن بيانات الطلاب.