منصفانہ شفلنگ کی ریاضی

شفل ایک واضح ریاضیاتی سوال پیش کرتا ہے: n مختلف اشیاء دی گئی ہوں تو n! ممکنہ ترتیبوں میں سے ایک پیدا کریں، ہر ایک یکساں امکان کے ساتھ۔ 10 عدد صحیح کے لیے، اس کا مطلب ہے 3,628,800 ترتیبیں۔ اوپر دکھائی گئی ترتیب اس جگہ سے یکساں امکان کے ساتھ منتخب کی گئی تھی، جو مکمل طور پر آپ کے براؤزر میں Fisher-Yates الگورتھم اور Web Cryptography API کا استعمال کرتے ہوئے تیار کی گئی۔

Fisher-Yates: حتمی الگورتھم

رونالڈ فشر اور فرینک ییٹس نے اصل شفلنگ طریقہ اپنی 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! سے ناقابل تقسیم ہے، کچھ ترتیبیں دوسروں سے زیادہ ممکن ہو جاتی ہیں۔ Fisher-Yates الگورتھم اس سے مکمل طور پر بچتا ہے۔

ترتیبوں کا حیران کن پیمانہ

فیکٹوریل نمو ہر دوسرے عام ریاضیاتی فنکشن سے آگے نکل جاتی ہے۔ دس آئٹمز 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 کارڈ کی معیاری ڈیک کے رِفل شفل کو مناسب بے ترتیبی تک پہنچنے کے لیے بالکل سات تکرار درکار ہیں۔ ڈیجیٹل Fisher-Yates شفل وہ کام حاصل کرتا ہے جو سات جسمانی رِفل شفلز تقریباً کرتے ہیں: ایک کمپیوٹیشنل گزر میں مکمل یکساں بے ترتیبی۔

کلاس روم میں

ہر طالب علم سے /sequence/1/10 کھولنے اور ایک بار شفل کرنے کو کہیں۔ پھر پوچھیں: کیا کسی دو طالب علموں نے ایک جیسی ترتیب بنائی؟ 3,628,800 ممکنہ ترتیبوں کے ساتھ، مماثلت غیر معمولی طور پر ناممکن ہے۔ پروجیکٹر مظاہرے کے لیے، /sequence/1/52 کھولیں اور بار بار شفل کریں۔ واضح حلقے ہر بار نئے نمونوں میں بکھر جاتے ہیں، جس سے بے ترتیبی فوری طور پر نظر آتی ہے۔ ٹول کو کسی اکاؤنٹ کی ضرورت نہیں، کوئی کوکیز سیٹ نہیں کرتا، اور کوئی طالب علم کا ڈیٹا محفوظ نہیں کرتا۔