Fisher–Yates shuffle
فشر-یٹس شفل ایک محدود ترتیب کو تبدیل کرنے کے لیے ایک الگورتھم ہے۔ الگورتھم ترتیب کے تمام عناصر کی فہرست لیتا ہے، اور فہرست سے کسی عنصر کو تصادفی طور پر کھینچ کر مسلسل شفلڈ ترتیب میں اگلے عنصر کا تعین کرتا ہے جب تک کہ کوئی عنصر باقی نہ رہے۔ الگورتھم ایک غیر جانبدار ترتیب پیدا کرتا ہے: ہر ترتیب کا یکساں امکان ہوتا ہے۔ الگورتھم کا جدید ورژن شفل ہونے والی اشیاء کی تعداد کے متناسب وقت لیتا ہے اور انہیں اپنی جگہ پر شفل کرتا ہے۔ فشر-یٹس شفل کا نام رونالڈ فشر اور فرینک یٹس کے نام پر رکھا گیا ہے، جنہوں نے سب سے پہلے اسے بیان کیا تھا، اور اسے ڈونلڈ نوتھ کے نام پر نوتھ شفل کے نام سے بھی جانا جاتا ہے۔ فشر-یٹس شفل کی ایک قسم، جسے سیٹولو کا الگورتھم کہا جاتا ہے، بے ترتیب تغیرات کے بجائے لمبائی n کی بے ترتیب چکور تغیرات پیدا کرنے کے لیے استعمال کیا جا سکتا ہے۔ فشر اور یٹس کا اصل طریقہ فشر-یٹس شفل، اپنی اصل شکل میں، 1938 میں رونالڈ فشر اور فرینک یٹس نے اپنی کتاب شماریاتی جدول برائے حیاتیاتی، زرعی اور طبی تحقیق میں بیان کیا تھا۔ الگورتھم کی ان کی تفصیل میں پنسل اور کاغذ کا استعمال کیا گیا ؛ بے ترتیب نمبروں کی ایک میز بے ترتیب فراہم کرتی ہے۔ 1 سے N تک کے نمبروں کی بے ترتیب ترتیب پیدا کرنے کے لیے دیا گیا بنیادی طریقہ مندرجہ ذیل ہے: 1 سے N تک کے نمبروں کو لکھیں۔ ایک اور بقیہ (بشمول) غیر متزلزل نمبروں کی تعداد کے درمیان ایک بے ترتیب نمبر k منتخب کریں۔ نچلے سرے سے گنتی کرتے ہوئے، kth نمبر نکالیں جو ابھی ختم نہیں ہوا ہے، اور اسے ایک علیحدہ فہرست کے آخر میں لکھیں۔ مرحلہ 2 سے دہرائیں جب تک کہ تمام نمبر ختم نہ ہو جائیں۔ مرحلہ 3 میں لکھے گئے نمبروں کی ترتیب اب اصل نمبروں کی بے ترتیب ترتیب ہے۔ بشرطیکہ مذکورہ بالا مرحلہ 2 میں منتخب کردہ بے ترتیب نمبر واقعی بے ترتیب اور غیر جانبدار ہوں، اسی طرح نتیجہ خیز ترتیب بھی ہوگی۔ فشر اور یٹس نے یہ بیان کرنے کا خیال رکھا کہ فراہم کردہ ٹیبلز سے کسی بھی مطلوبہ رینج میں اس طرح کے بے ترتیب نمبروں کو اس انداز میں کیسے حاصل کیا جائے جس سے کسی تعصب سے بچا جا سکے۔ انہوں نے ایک آسان طریقہ استعمال کرنے کا امکان بھی تجویز کیا-ایک سے این تک بے ترتیب نمبروں کو چننا اور کسی بھی ڈپلیکیٹ کو چھوڑنا-ترتیب کے پہلے نصف حصے کو پیدا کرنے کے لیے، اور صرف باقی نصف میں زیادہ پیچیدہ الگورتھم کا اطلاق کرنا، جہاں ڈپلیکیٹ نمبر کا انتخاب بصورت دیگر مایوس کن طور پر عام ہو جائے گا۔ جدید الگورتھم فشر-یٹس شفل کا جدید ورژن، جو کمپیوٹر کے استعمال کے لیے ڈیزائن کیا گیا تھا، رچرڈ ڈرسٹن فیلڈ نے 1964 میں متعارف کرایا تھا اور ڈونلڈ ای نوتھ نے دی آرٹ آف کمپیوٹر پروگرامنگ میں "الگورتھم پی (شفلنگ)" کے طور پر مقبول کیا تھا۔ نہ تو ڈرسٹن فیلڈ کے مضمون اور نہ ہی نوتھ کے دی آرٹ آف کمپیوٹر پروگرامنگ کے پہلے ایڈیشن نے فشر اور یٹس کے کام کو تسلیم کیا ؛ وہ شاید اس سے واقف نہیں تھے۔ نوتھ کے دی آرٹ آف کمپیوٹر پروگرامنگ کے بعد کے ایڈیشنوں میں فشر اور یٹس کی شراکت کا ذکر ہے۔ ڈرسٹن فیلڈ کی طرف سے بیان کردہ الگورتھم فشر اور یٹس کی طرف سے دیئے گئے الگورتھم سے زیادہ موثر ہے: جبکہ فشر اور یٹس کے طریقہ کار کا ایک سادہ کمپیوٹر نفاذ اوپر کے مرحلہ 3 میں بقیہ نمبروں کو گننے میں غیر ضروری وقت گزارے گا، ڈرسٹن فیلڈ کا حل یہ ہے کہ "اسٹرک" نمبروں کو ہر تکرار پر آخری غیر متزلزل نمبر کے ساتھ تبدیل کرکے فہرست کے آخر میں منتقل کیا جائے۔ یہ سادہ نفاذ کے مقابلے میں الگورتھم کی وقت کی پیچیدگی کو کم کرتا ہے۔ یہ تبدیلی مندرجہ ذیل الگورتھم (صفر پر مبنی صف کے لیے) دیتی ہے۔ --n عناصر کی صف a کو شفل کرنے کے لیے (اشاریہ جات 0.n-1): i کے لیے n−1 سے 1 تک بے ترتیب عدد اس طرح کریں کہ 0 ≤ j ≤ i کا تبادلہ a [j] اور a [i] ایک مساوی ورژن جو صف کو مخالف سمت میں شفل کرتا ہے (سب سے نچلے انڈیکس سے سب سے اوپر تک) یہ ہے:-- n عناصر کی صف a کو شفل کرنے کے لیے (اشاریہ جات 0.n-1): i کے لیے 0 سے n−2 تک بے ترتیب عدد اس طرح کریں کہ i ≤ j <n کا تبادلہ a [i] اور a [j] مثالیں پنسل اور کاغذ کا طریقہ یہ مثال فشر اور یٹس کے اصل طریقہ کا استعمال کرتے ہوئے A سے H تک کے حروف کو ترتیب دیتی ہے، شروع کرتے ہوئے۔ اگر جے = 3، مثال کے طور پر، تو تیسرا حرف سکریچ پیڈ پر مارا جاتا ہے اور اسے اس کے نتیجے میں لکھا جاتا ہے: دوسرا بے ترتیب نمبر منتخب کیا جاتا ہے، اس بار 1 سے 7 تک۔ اگر نمبر 4 ہے، تو کوئی چوتھے حرف کو باہر نکالتا ہے جو ابھی تک سکریچ پیڈ سے نہیں مارا گیا ہے اور اسے نتیجہ میں شامل کرتا ہے: اگلا بے ترتیب نمبر 1 سے 6 تک منتخب کیا جاتا ہے، اور پھر 1 سے 5 تک، اور اسی طرح، ہمیشہ اسٹرائیک آؤٹ عمل کو اوپر کی طرح دہرایا جاتا ہے: جدید طریقہ ڈرسٹن فیلڈ کے الگورتھم کے ورژن میں، منتخب کردہ حروف کو باہر نکالنے اور انہیں کہیں اور کاپی کرنے کے بجائے، انہیں آخری حرف کے ساتھ تبدیل کیا جاتا ہے جو ابھی تک منتخب نہیں کیا گیا ہے۔ پہلے کی طرح A سے H تک کے حروف سے شروع کریں: 1 سے 8 تک کا بے ترتیب نمبر J منتخب کریں، اور پھر jth اور 8 ویں حروف کو تبدیل کریں۔ لہذا، اگر بے ترتیب نمبر 6 ہے، مثال کے طور پر، فہرست میں چھٹے اور آٹھویں حروف کو تبدیل کریں: اگلا بے ترتیب نمبر 1 سے 7 تک منتخب کیا جاتا ہے، اور منتخب کردہ حرف کو ساتویں حرف کے ساتھ تبدیل کیا جاتا ہے۔ اگر یہ 2 ہے، مثال کے طور پر، دوسرے اور ساتویں حروف کو تبدیل کریں: یہ عمل اس وقت تک دہرایا جاتا ہے جب تک کہ ترتیب مکمل نہ ہو جائے: آٹھ مراحل کے بعد، الگورتھم مکمل ہو جاتا ہے اور اس کے نتیجے میں ترتیب G E D C A H B F ہے۔ متغیرات "انسائیڈ آؤٹ" الگورتھم فشر-یٹس شفل، جیسا کہ ڈرسٹن فیلڈ نے نافذ کیا ہے، ایک ان پلیس شفل ہے۔ یعنی، ایک ابتدائی صف کو دیکھتے ہوئے، یہ صف کی شفل شدہ کاپی تیار کرنے کے بجائے صف کے عناصر کو اپنی جگہ پر شفل کرتا ہے۔ یہ ایک فائدہ ہو سکتا ہے اگر شفل کی جانے والی صف بڑی ہو۔ ایک صف کو بیک وقت شروع کرنے اور شفل کرنے کے لیے، شفل کا "انسائیڈ آؤٹ" ورژن کرکے تھوڑی زیادہ کارکردگی حاصل کی جا سکتی ہے۔ اس ورژن میں، عنصر نمبر i کو صف میں پہلی i پوزیشنوں کے درمیان ایک بے ترتیب پوزیشن میں رکھا جاتا ہے، اس عنصر کو منتقل کرنے کے بعد جو پہلے اس پوزیشن پر قابض تھا پوزیشن i پر۔ اگر بے ترتیب پوزیشن نمبر i ہوتی ہے، تو اس "حرکت" (اسی جگہ پر) میں ایک غیر ابتدائی قدر شامل ہوتی ہے، لیکن اس سے کوئی فرق نہیں پڑتا، کیونکہ اس کے بعد قیمت کو فوری طور پر ختم کر دیا جاتا ہے۔ کسی علیحدہ شروعات کی ضرورت نہیں ہے، اور کوئی تبادلہ نہیں کیا جاتا ہے۔ عام صورت میں جہاں ماخذ کی تعریف کسی سادہ فنکشن سے کی جاتی ہے، جیسے کہ 0 سے n−1 تک کے انٹیجرز، ماخذ کو آسانی سے فنکشن سے تبدیل کیا جا سکتا ہے کیونکہ عمل کے دوران ماخذ کو کبھی تبدیل نہیں کیا جاتا ہے۔ n عناصر کی صف a کو ماخذ کی تصادفی طور پر شفل شدہ کاپی میں شروع کرنے کے لیے، دونوں 0 پر مبنی: i کے لیے 0 سے n−1 تک بے ترتیب عدد اس طرح کریں کہ 0 ≤ j ≤ i اگر j ≤ i a [i] ≤ a [j] a [j] ≤ ماخذ [i] اندر سے باہر شفل کو انڈکشن کے ذریعے درست دیکھا جا سکتا ہے۔ ایک کامل بے ترتیب نمبر جنریٹر فرض کرتے ہوئے، ہر ایک n! بے ترتیب نمبروں کے مختلف سلسلے جو بے ترتیب کالوں سے حاصل کیے جا سکتے ہیں وہ اقدار کی ایک مختلف ترتیب پیدا کریں گے، لہذا یہ سب بالکل ایک بار حاصل کیے جاتے ہیں۔ وہ شرط جو چیک کرتی ہے کہ آیا j ष्ण i کو ان زبانوں میں خارج کیا جا سکتا ہے جن میں غیر ابتدائی صف کی اقدار تک رسائی میں کوئی دشواری نہیں ہے۔ یہ Hn ≈ ln n + γ بے کار تفویض کی متوقع قیمت پر n مشروط شاخوں کو ختم کرتا ہے۔ اس تکنیک کا ایک اور فائدہ یہ ہے کہ n، ماخذ میں موجود عناصر کی تعداد، کو پہلے سے جاننے کی ضرورت نہیں ہے۔ ہمیں صرف ماخذ کے اعداد و شمار کے اختتام کا پتہ لگانے کے قابل ہونے کی ضرورت ہے جب وہ پہنچ جائے۔ صف کے نیچے a کو خالی سے شروع کرتے ہوئے بار بار بنایا جاتا ہے، اور a.length دیکھے گئے عناصر کی موجودہ تعداد کی نمائندگی کرتا ہے۔ خالی صف a کو ماخذ کی تصادفی طور پر شفل شدہ کاپی میں شروع کرنے کے لیے جس کی لمبائی معلوم نہیں ہے: جبکہ source.moreDataAvailable j-بے ترتیب عدد اس طرح ہے کہ 0 ≤ j ≤ a.length اگر j = a.length a.append (source.next) اور a.append (a [[j]) a [j] → source.next سیٹولو کا الگورتھم ایک بہت ہی مماثل الگورتھم 1986 میں سینڈرا سیٹولو نے (زیادہ سے زیادہ) لمبائی n کے یکساں طور پر تقسیم شدہ چکروں کو پیدا کرنے کے لیے شائع کیا تھا۔ ڈرسٹن فیلڈ اور سیٹولو کے الگورتھم کے درمیان صرف فرق یہ ہے کہ مؤخر الذکر میں، اوپر والے مرحلے 2 میں، بے ترتیب نمبر j کو درمیان کی حد سے منتخب کیا گیا ہے۔ یہ سادہ سی تبدیلی الگورتھم میں ترمیم کرتی ہے تاکہ نتیجے میں ہونے والی ترتیب ہمیشہ ایک ہی چکر پر مشتمل ہو۔ درحقیقت، جیسا کہ ذیل میں بیان کیا گیا ہے، جب عام فشر-یٹس شفل کا ارادہ کیا جاتا ہے تو اتفاقی طور پر سیٹولو کے الگورتھم کو نافذ کرنا کافی آسان ہوتا ہے۔ یہ (n−1) کے چھوٹے سیٹ سے ترتیبات کو چن کر نتائج کا تعصب کرے گا! تمام n کے مکمل سیٹ کے بجائے لمبائی N کے سائیکل! ممکنہ تغیرات۔ حقیقت یہ ہے کہ ستولو کا الگورتھم ہمیشہ لمبائی n کا ایک چکر پیدا کرتا ہے جسے انڈکشن کے ذریعے دکھایا جا سکتا ہے۔ انڈکشن کے ذریعے فرض کریں کہ لوپ کی ابتدائی تکرار کے بعد، بقیہ تکرار پہلے n−1 عناصر کو لمبائی n−1 کے چکر کے مطابق پرموٹ کرتی ہیں (وہ بقیہ تکرار صرف سیٹولو کا الگورتھم ہے جو ان پہلے n−1 عناصر پر لاگو ہوتا ہے)۔ اس کا مطلب یہ ہے کہ ابتدائی عنصر کو اس کی نئی پوزیشن p پر ٹریس کرنا، پھر اصل میں پوزیشن p پر موجود عنصر کو اس کی نئی پوزیشن پر لانا، اور اسی طرح، کوئی بھی دیگر تمام پوزیشنوں کا دورہ کرنے کے بعد ہی ابتدائی پوزیشن پر واپس آتا ہے۔ فرض کریں کہ ابتدائی تکرار نے حتمی عنصر کو (غیر حتمی) پوزیشن k پر ایک کے ساتھ تبدیل کر دیا، اور یہ کہ پہلے n−1 عناصر کے بعد کے تکرار نے اسے پوزیشن l پر منتقل کر دیا۔ ہم تمام n عناصر کے تکرار کا موازنہ پہلے n−1 عناصر کے بقیہ تکرار σ سے کرتے ہیں۔ جیسا کہ ابھی ذکر کیا گیا ہے، یکے بعد دیگرے پوزیشنوں کا پتہ لگانے سے، پوزیشن k پر پہنچنے تک π اور σ کے درمیان کوئی فرق نہیں ہوتا ہے۔ لیکن پھر، π کے تحت اصل پوزیشن k پر موجود عنصر کو پوزیشن l کے بجائے آخری پوزیشن پر منتقل کر دیا جاتا ہے، اور اصل میں آخری پوزیشن پر موجود عنصر کو پوزیشن l پر منتقل کر دیا جاتا ہے۔ وہاں سے، π کے لیے پوزیشنوں کی ترتیب دوبارہ σ کے لیے ترتیب کی پیروی کرتی ہے، اور ضرورت کے مطابق ابتدائی پوزیشن پر واپس آنے سے پہلے تمام پوزیشنوں کا دورہ کیا جائے گا۔ جہاں تک تغیرات کے مساوی امکان کا تعلق ہے، یہ مشاہدہ کرنا کافی ہے کہ ترمیم شدہ الگورتھم میں (n−1) شامل ہے! بے ترتیب نمبروں کے الگ الگ ممکنہ سلسلے، جن میں سے ہر ایک واضح طور پر ایک مختلف ترتیب پیدا کرتا ہے، اور جن میں سے ہر ایک ہوتا ہے-یہ فرض کرتے ہوئے کہ بے ترتیب نمبر کا ماخذ غیر جانبدار ہے-مساوی امکان کے ساتھ۔ (n − 1)! اس طرح پیدا ہونے والی مختلف تغیرات لمبائی n کے چکروں کے سیٹ کو قطعی طور پر ختم کر دیتی ہیں: اس طرح کے ہر چکر میں حتمی پوزیشن میں n کی قدر کے ساتھ ایک منفرد سائیکل نوٹیشن ہوتا ہے، جو (n−1) کی اجازت دیتا ہے! سائیکل نوٹیشن کی دیگر پوزیشنوں کو پر کرنے کے لیے بقیہ اقدار کی تغیرات۔ پائیتھن میں سیٹولو کے الگورتھم کا ایک نمونہ نفاذ یہ ہے: بے ترتیب درآمد سے رینڈرانج ڈیف سیٹولو _ سائیکل (آئٹمز)-> کوئی نہیں: "" سیٹولو کا الگورتھم "۔ آئی = لین (آئٹمز) جبکہ آئی> 1: آئی = آئی-1 جے = رینڈرینج (آئی) #0 <= جے <= آئی-1 آئٹمز [جے]، آئٹمز [آئی] = آئٹمز [آئی]، آئٹمز [جے] دوسرے شفلنگ الگورتھم کے ساتھ موازنہ فشر-یٹس شفل کا ایسمپٹوٹک ٹائم اور اسپیس پیچیدگی زیادہ سے زیادہ ہے۔ اعلی معیار کے غیر جانبدار بے ترتیب نمبر ماخذ کے ساتھ مل کر، اس کے غیر جانبدار نتائج پیدا کرنے کی بھی ضمانت دی جاتی ہے۔ کچھ دوسرے حلوں کے مقابلے میں، اس کا یہ فائدہ بھی ہے کہ، اگر نتیجے میں ہونے والی ترتیب کے صرف ایک حصے کی ضرورت ہو تو، اسے آدھے راستے سے روکا جا سکتا ہے، یا یہاں تک کہ روکا جا سکتا ہے اور بار بار دوبارہ شروع کیا جا سکتا ہے، جس سے ضرورت کے مطابق ترتیب میں اضافہ ہوتا ہے۔ سادہ طریقہ ہر عنصر کو تمام عناصر میں سے تصادفی طور پر منتخب کردہ دوسرے عنصر کے ساتھ تبدیل کرنے کا سادہ طریقہ متعصبانہ ہے۔ مختلف ترتیبات میں پیدا ہونے کے مختلف امکانات ہوں گے، ہر ایک کے لیے، کیونکہ مختلف ترتیبات کی تعداد، الگورتھم کے بے ترتیب نتائج کی تعداد کو یکساں طور پر تقسیم نہیں کرتی ہے۔ خاص طور پر، برٹرینڈ کے مفروضے کے مطابق اور کے درمیان کم از کم ایک پرائم نمبر ہوگا، اور یہ نمبر تقسیم ہوگا لیکن تقسیم نہیں ہوگا۔ بے ترتیب درآمد سے رینڈرانج ڈیف نییو _ شفل (آئٹمز)-> کوئی نہیں: "" ایک سادہ طریقہ۔ یہ اس بات کی ایک مثال ہے کہ کیا نہیں کرنا چاہیے-اس کے بجائے فشر-یٹس کا استعمال کریں۔ n = لین (آئٹمز) i کے لیے رینج (n) میں: j = رینڈرینج (n) #0 <= j <= n-1 آئٹمز [j]، آئٹمز [i] = آئٹمز [i]، آئٹمز [j] ترتیب دینا ایک متبادل طریقہ سیٹ کے ہر عنصر کو بے ترتیب نمبر تفویض کرتا ہے جسے شفل کیا جانا ہے اور پھر سیٹ کو تفویض کردہ نمبروں کے مطابق ترتیب دیتا ہے۔ چھانٹنے کے طریقہ کار میں فشر-یٹس کی طرح ہی غیر علامتی وقت کی پیچیدگی ہے: اگرچہ عام چھانٹ O (n لاگ n) ہے، لیکن اعداد کو O (n) وقت میں ریڈکس چھانٹ کا استعمال کرتے ہوئے مؤثر طریقے سے ترتیب دیا جاتا ہے۔ فشر-یٹس شفل کی طرح، چھانٹ کا طریقہ غیر جانبدار نتائج پیدا کرتا ہے۔ تاہم، اس بات کو یقینی بنانے کے لیے خیال رکھنا چاہیے کہ تفویض کردہ بے ترتیب نمبر کبھی بھی ڈپلیکیٹ نہ ہوں، کیونکہ ترتیب دینے والے الگورتھم عام طور پر ٹائی کی صورت میں عناصر کو بے ترتیب آرڈر نہیں کرتے ہیں۔ مزید برآں، اس طریقہ کار کے لیے غیر علامتی طور پر بڑی جگہ کی ضرورت ہوتی ہے: O (n) بے ترتیب نمبروں کے لیے اضافی اسٹوریج کی جگہ، بمقابلہ فشر-یٹس شفل کے لیے O (1) جگہ۔ آخر میں، چھانٹنے کے طریقہ کار کا ایک سادہ متوازی نفاذ ہوتا ہے، فشر-یٹس شفل کے برعکس، جو کہ ترتیب وار ہوتا ہے۔ مندرجہ بالا طریقہ کار کا ایک متغیر جس نے ایسی زبانوں میں کچھ استعمال دیکھا ہے جو صارف کے مخصوص موازنہ افعال کے ساتھ ترتیب دینے کی حمایت کرتی ہیں، وہ ہے فہرست کو ایک موازنہ فنکشن کے ساتھ ترتیب دے کر شفل کرنا جو بے ترتیب اقدار واپس کرتا ہے۔ تاہم، اس سے انتہائی غیر یکساں تقسیم پیدا ہونے کا بہت امکان ہے، جو اس کے علاوہ استعمال شدہ چھانٹنے والے الگورتھم پر بہت زیادہ انحصار کرتا ہے۔ مثال کے طور پر فرض کریں کہ کوئکسورٹ کو ترتیب دینے والے الگورتھم کے طور پر استعمال کیا جاتا ہے، جس میں ایک مقررہ عنصر کو پہلے محور عنصر کے طور پر منتخب کیا جاتا ہے۔ الگورتھم محور کا موازنہ دوسرے تمام عناصر سے کرنا شروع کر دیتا ہے تاکہ انہیں ان کم اور اس سے بڑے عناصر میں الگ کیا جا سکے، اور ان گروپوں کے متعلقہ سائز محور عنصر کی حتمی جگہ کا تعین کریں گے۔ یکساں طور پر تقسیم شدہ بے ترتیب ترتیب کے لیے، محور عنصر کے لیے ہر ممکنہ حتمی پوزیشن کا یکساں امکان ہونا چاہیے، لیکن اگر ہر ابتدائی موازنہ مساوی امکان کے ساتھ "کم" یا "زیادہ" واپس کرتا ہے، تو اس پوزیشن میں p = 1/2 کے لیے بائنومیل تقسیم ہوگی، جو ترتیب کے وسط کے قریب پوزیشنوں کو سروں کے قریب پوزیشنوں کے مقابلے میں بہت زیادہ امکان کے ساتھ دیتا ہے۔ دوسرے چھانٹنے کے طریقوں جیسے ضم کی ترتیب پر لاگو بے ترتیب موازنہ افعال ایسے نتائج پیدا کر سکتے ہیں جو زیادہ یکساں نظر آتے ہیں، لیکن بالکل بھی نہیں ہیں، کیونکہ دو ترتیبات کو بار بار مساوی امکانات کے ساتھ منتخب کرکے ضم کرنا (جب تک کہ انتخاب ایک ترتیب کے ختم ہونے سے مجبور نہ ہو جائے) یکساں تقسیم کے ساتھ نتائج پیدا نہیں کرتا ہے۔ اس کے بجائے کسی ترتیب کو منتخب کرنے کا امکان اس میں باقی عناصر کی تعداد کے متناسب ہونا چاہیے۔ درحقیقت کوئی بھی ایسا طریقہ جو مساوی امکانات کے ساتھ صرف دو طرفہ بے ترتیب واقعات کا استعمال کرتا ہو ("سکے پلٹنا")، ایک محدود تعداد میں بار بار دہرایا جاتا ہے، یکساں تقسیم کے ساتھ ایک ترتیب (دو سے زیادہ عناصر کے) کی تغیرات پیدا کر سکتا ہے، کیونکہ ہر عمل کے راستے میں امکان کے طور پر ایک عقلی نمبر ہوگا جس میں ڈینومینیٹر کے طور پر 2 کی طاقت ہوگی، جبکہ مطلوبہ امکان 1/n ہوگا! ہر ممکنہ ترتیب کے لیے اس شکل کا نہیں ہے۔ اصولی طور پر یہ شفلنگ طریقہ پروگرام کی ناکامیوں جیسے لامتناہی لوپس یا رسائی کی خلاف ورزیوں کا باعث بھی بن سکتا ہے، کیونکہ چھانٹنے والے الگورتھم کی درستگی آرڈر ریلیشن (جیسے ٹرانزٹیویٹی) کی خصوصیات پر منحصر ہو سکتی ہے جو بے ترتیب اقدار پیدا کرنے والے موازنہ میں یقینی طور پر نہیں ہوگی۔ اگرچہ اس قسم کا طرز عمل ترتیب دینے والے معمولات کے ساتھ نہیں ہونا چاہیے جو کبھی بھی موازنہ نہیں کرتا ہے جس کے نتائج کی یقین کے ساتھ پیش گوئی کی جا سکتی ہے (پچھلے موازنہ کی بنیاد پر)، جان بوجھ کر اس طرح کے موازنہ کرنے کی درست وجوہات ہو سکتی ہیں۔ مثال کے طور پر یہ حقیقت کہ کسی بھی عنصر کا اپنے برابر موازنہ کرنا چاہیے، انہیں کارکردگی کی وجوہات کی بناء پر سینٹینل ویلیو کے طور پر استعمال کرنے کی اجازت دیتا ہے، اور اگر ایسا ہے تو، ایک بے ترتیب موازنہ فنکشن چھانٹنے والے الگورتھم کو توڑ دے گا۔ فشر-یٹس شفل کو نافذ کرتے وقت تعصب کے ممکنہ ذرائع کی دیکھ بھال کی جانی چاہیے، دونوں الگورتھم کے نفاذ میں اور بے ترتیب نمبروں کی نسل میں جس پر یہ بنایا گیا ہے، بصورت دیگر نتائج پتہ لگانے کے قابل تعصب ظاہر کر سکتے ہیں۔ تعصب کے متعدد عام ذرائع ذیل میں درج کیے گئے ہیں۔ عمل درآمد کی غلطیاں فشر-یٹس شفل کو لاگو کرتے وقت ایک عام غلطی غلط رینج سے بے ترتیب نمبروں کا انتخاب کرنا ہے۔ ناقص الگورتھم صحیح طریقے سے کام کرتا دکھائی دے سکتا ہے، لیکن یہ ہر ممکنہ ترتیب کو مساوی امکان کے ساتھ پیدا نہیں کرے گا، اور ہو سکتا ہے کہ یہ کچھ ترتیبات بالکل پیدا نہ کرے۔ مثال کے طور پر، ایک عام آف-بائی-ون غلطی یہ ہوگی کہ اوپر کی مثال میں تبادلے کے لیے اندراج کے انڈیکس جے کا انتخاب ہمیشہ اندراج کے انڈیکس i سے سختی سے کم ہو جس کے ساتھ اسے تبدیل کیا جائے گا۔ یہ فشر-یٹس شفل کو سیٹولو کے الگورتھم میں بدل دیتا ہے، جو تمام عناصر پر مشتمل ایک ہی چکر پر مشتمل صرف تغیرات پیدا کرتا ہے: خاص طور پر، اس ترمیم کے ساتھ، صف کا کوئی عنصر کبھی بھی اپنی اصل پوزیشن میں ختم نہیں ہو سکتا۔ اسی طرح، ہمیشہ ہر تکرار پر درست صف اشاریہ جات کی پوری رینج میں سے جے کا انتخاب بھی ایک ایسا نتیجہ پیدا کرتا ہے جو متعصبانہ ہوتا ہے، حالانکہ کم واضح طور پر ایسا ہوتا ہے۔ یہ اس حقیقت سے دیکھا جا سکتا ہے کہ ایسا کرنے سے تبادلوں کے مختلف ممکنہ سلسلے حاصل ہوتے ہیں، جبکہ صرف n! ہوتے ہیں۔ کسی n-عنصر صف کی ممکنہ تغیرات۔ چونکہ nn کو کبھی بھی n سے یکساں طور پر تقسیم نہیں کیا جا سکتا! جب n> 2 (جیسا کہ مؤخر الذکر n − 1 سے تقسیم ہوتا ہے، جو n کے ساتھ کوئی بنیادی عوامل کا اشتراک نہیں کرتا ہے)، تو کچھ تغیرات دوسروں کے مقابلے میں تبادلوں کے زیادہ nn ترتیبات سے پیدا ہونے چاہئیں۔ اس تعصب کی ایک ٹھوس مثال کے طور پر، تین عناصر کی صف [1، 2، 3] کو تبدیل کرنے کے ممکنہ نتائج کی تقسیم کا مشاہدہ کریں۔ اس صف میں 6 ممکنہ تغیرات ہیں (3! = 6)، لیکن الگورتھم 27 ممکنہ شفلز (33 = 27) پیدا کرتا ہے۔ اس صورت میں، [1، 2، 3]، [3، 1، 2]، اور [3، 2، 1] ہر ایک 27 شفلوں میں سے 4 کا نتیجہ ہے، جبکہ باقی 3 میں سے ہر ایک 27 شفلوں میں سے 5 میں ہوتا ہے۔ دائیں طرف کا میٹرکس لمبائی 7 کی فہرست میں ہر عنصر کے کسی دوسری پوزیشن میں ختم ہونے کے امکان کو ظاہر کرتا ہے۔ مشاہدہ کریں کہ زیادہ تر عناصر کے لیے، ان کی اصل پوزیشن (میٹرکس کا مرکزی اخترن) میں ختم ہونے کا امکان سب سے کم ہوتا ہے، اور ایک سلاٹ کو پیچھے کی طرف منتقل کرنے کا امکان سب سے زیادہ ہوتا ہے۔ ماڈیولو بائیس فشر-یٹس شفل کرنے میں مختلف حدود سے یکساں طور پر تقسیم شدہ بے ترتیب انٹیجرز کو چننا شامل ہے۔ زیادہ تر بے ترتیب نمبر جنریٹر، تاہم-چاہے سچ ہوں یا فرضی-صرف براہ راست 0 سے RAND _ MAX تک ایک مقررہ رینج میں نمبر فراہم کریں گے، اور کچھ لائبریریوں میں، RAND _ MAX 32767 تک کم ہو سکتا ہے۔ اس طرح کے نمبروں کو مطلوبہ رینج میں مجبور کرنے کا ایک آسان اور عام طور پر استعمال ہونے والا طریقہ ماڈیولو آپریٹر کا اطلاق کرنا ہے ؛ یعنی، انہیں رینج کے سائز سے تقسیم کرنا اور بقیہ لینا۔ تاہم، 0-1 سے 0-n تک ہر رینج میں بے ترتیب نمبر پیدا کرنے کے لیے فشر-یٹس شفل کی ضرورت تقریبا اس بات کی ضمانت دیتی ہے کہ ان میں سے کچھ رینج بے ترتیب نمبر جنریٹر کی قدرتی رینج کو یکساں طور پر تقسیم نہیں کریں گے۔ اس طرح، بقیہ کو ہمیشہ یکساں طور پر تقسیم نہیں کیا جائے گا اور اس سے بھی بدتر بات یہ ہے کہ تعصب منظم طریقے سے چھوٹے بقیہ کے حق میں ہوگا۔ مثال کے طور پر، فرض کریں کہ آپ کا بے ترتیب نمبر سورس 0 سے 99 تک کے نمبر دیتا ہے (جیسا کہ فشر اور یٹس کی اصل ٹیبلز کا معاملہ تھا)، اور یہ کہ آپ 0 سے 15 تک ایک غیر جانبدار بے ترتیب نمبر حاصل کرنا چاہتے ہیں۔ اگر آپ صرف اعداد کو 16 سے تقسیم کرتے ہیں اور بقیہ کو لیتے ہیں، تو آپ دیکھیں گے کہ 0-3 اعداد دوسروں کے مقابلے میں تقریبا 17 فیصد زیادہ ہوتے ہیں۔ اس کی وجہ یہ ہے کہ 16 100 کو یکساں طور پر تقسیم نہیں کرتا: 100 سے کم یا اس کے برابر 16 کا سب سے بڑا ضرب 6 × 16 = 96 ہے، اور یہ نامکمل حد 96-99 میں موجود اعداد ہیں جو تعصب کا سبب بنتے ہیں۔ اس مسئلے کو حل کرنے کا سب سے آسان طریقہ یہ ہے کہ بقیہ کو لینے سے پہلے ان نمبروں کو ضائع کر دیا جائے اور اس وقت تک دوبارہ کوشش کرتے رہیں جب تک کہ مناسب رینج میں کوئی نمبر سامنے نہ آئے۔ اگرچہ اصولی طور پر یہ، بدترین صورت میں، ہمیشہ کے لیے لگ سکتا ہے، دوبارہ کوششوں کی متوقع تعداد ہمیشہ ایک سے کم ہوگی۔ ایک متعلقہ مسئلہ نفاذ کے ساتھ ہوتا ہے جو پہلے بے ترتیب فلوٹنگ پوائنٹ نمبر تیار کرتا ہے-عام طور پر رینج میں [0,1]-اور پھر اسے مطلوبہ رینج کے سائز سے ضرب دیں اور نیچے گول کریں۔ یہاں مسئلہ یہ ہے کہ بے ترتیب فلوٹنگ پوائنٹ نمبر، اگرچہ احتیاط سے تیار کیے گئے ہوں، ہمیشہ صرف محدود درستگی رکھتے ہیں۔ اس کا مطلب یہ ہے کہ کسی بھی رینج میں ممکنہ فلوٹنگ پوائنٹ ویلیوز کی صرف ایک محدود تعداد ہوتی ہے، اور اگر رینج کو کئی حصوں میں تقسیم کیا جاتا ہے جو اس نمبر کو یکساں طور پر تقسیم نہیں کرتے ہیں، تو کچھ حصے دوسروں کے مقابلے میں زیادہ ممکنہ ویلیوز کے ساتھ ختم ہو جائیں گے۔ اگرچہ نتیجے میں ہونے والا تعصب وہی منظم نیچے کی طرف رجحان نہیں دکھائے گا جیسا کہ پچھلے معاملے میں تھا، لیکن یہ تب بھی موجود رہے گا۔ سیوڈورانڈم جنریٹر ایک اضافی مسئلہ اس وقت پیدا ہوتا ہے جب فشر-یٹس شفل کو سیوڈورانڈم نمبر جنریٹر یا پی آر این جی کے ساتھ استعمال کیا جاتا ہے: چونکہ اس طرح کے جنریٹر کے ذریعہ نمبروں کی پیداوار کا تسلسل مکمل طور پر ترتیب کے آغاز میں اس کی اندرونی حالت سے طے ہوتا ہے، اس طرح کے جنریٹر کے ذریعہ چلائی جانے والی شفل ممکنہ طور پر اس سے زیادہ واضح تغیرات پیدا نہیں کرسکتی ہے جس سے جنریٹر کی الگ ممکنہ ریاستیں ہوتی ہیں۔ یہاں تک کہ جب ممکنہ حالتوں کی تعداد تغیرات کی تعداد سے تجاوز کر جاتی ہے، تب بھی اعداد کے سلسلے سے لے کر تغیرات تک نقشہ سازی کی بے قاعدہ نوعیت کا مطلب یہ ہے کہ کچھ تغیرات دوسروں کے مقابلے میں زیادہ کثرت سے ہوں گے۔ اس طرح، تعصب کو کم کرنے کے لیے، پی آر این جی کی حالتوں کی تعداد کم از کم شدت کے کئی آرڈرز سے ترتیبات کی تعداد سے زیادہ ہونی چاہیے۔ مثال کے طور پر، بہت سی پروگرامنگ زبانوں اور/یا کتب خانوں کے ذریعہ فراہم کردہ بلٹ ان سیڈورینڈم نمبر جنریٹر میں اکثر اندرونی حالت کے صرف 32 بٹس ہو سکتے ہیں، جس کا مطلب ہے کہ یہ صرف اعداد کے 232 مختلف سلسلے تیار کر سکتا ہے۔ اگر اس طرح کے جنریٹر کو 52 تاشیوں کے ڈیک کو شفل کرنے کے لیے استعمال کیا جاتا ہے، تو یہ کبھی بھی 52 کا بہت چھوٹا حصہ ہی پیدا کر سکتا ہے! ≈ 2225.6 ممکنہ تغیرات۔ 226 بٹس سے کم اندرونی حالت والے جنریٹر کے لیے 52 کارڈ والے ڈیک کے تمام ممکنہ تغیرات پیدا کرنا ناممکن ہے۔ کوئی بھی سیوڈورانڈم نمبر جنریٹر ابتدائی نقطہ سے شروع کرتے ہوئے زیادہ الگ ترتیب پیدا نہیں کر سکتا، اس سے زیادہ کہ بیج کی الگ الگ اقدار ہیں جن کے ساتھ اسے شروع کیا جا سکتا ہے۔ اس طرح، ایک جنریٹر جس میں 1024 بٹس اندرونی حالت ہوتی ہے لیکن جسے 32 بٹ بیج کے ساتھ شروع کیا جاتا ہے وہ ابھی بھی شروع کرنے کے فورا بعد صرف 232 مختلف تغیرات پیدا کر سکتا ہے۔ اگر کوئی جنریٹر کو تعدد پیدا کرنے کے لیے استعمال کرنا شروع کرنے سے پہلے کئی بار استعمال کرتا ہے تو یہ مزید تعدد پیدا کر سکتا ہے، لیکن یہ بے ترتیب پن کو بڑھانے کا ایک بہت ہی غیر موثر طریقہ ہے: فرض کریں کہ کوئی جنریٹر کو ایک ارب تک کی بے ترتیب تعداد استعمال کرنے کا بندوبست کر سکتا ہے، جیسے کہ سادگی کے لیے 230، ابتدا اور تعدد پیدا کرنے کے درمیان کا وقت، پھر بھی ممکنہ تعدد کی تعداد صرف 262 ہے۔ ایک اور مسئلہ اس وقت پیدا ہوتا ہے جب ایک سادہ لکیری ہم آہنگ پی آر این جی کو اوپر بیان کردہ حد میں کمی کے تقسیم اور لے جانے والے طریقہ کار کے ساتھ استعمال کیا جاتا ہے۔ یہاں مسئلہ یہ ہے کہ ماڈیولو 2e کے ساتھ لکیری ہم آہنگ پی آر این جی کے نچلے درجے کے بٹس اعلی درجے کے بٹس کے مقابلے میں کم بے ترتیب ہوتے ہیں: جنریٹر کے نچلے n بٹس میں خود زیادہ سے زیادہ 2n کی مدت ہوتی ہے۔ جب تقسیم کنندہ دو کی طاقت ہے، تو بقیہ کو لازمی طور پر لینے کا مطلب ہائی آرڈر بٹس کو پھینکنا ہے، اس طرح کہ ایک نمایاں طور پر کم بے ترتیب قیمت کے ساتھ ختم ہوتا ہے۔ اگر ایل سی جی میں پرائم ماڈیولو ہو تو مختلف قوانین لاگو ہوتے ہیں، لیکن اس طرح کے جنریٹر غیر معمولی ہیں۔ یہ عام اصول کی ایک مثال ہے کہ ناقص معیار کا آر این جی یا پی آر این جی ناقص معیار کے شفلز پیدا کرے گا۔ آر سی 4 بھی دیکھیں، ایک اسٹریم سائفر جو ایک صف ریزروائر کے نمونے لینے پر مبنی ہے، خاص طور پر الگورتھم آر جو فشر-یٹس شفل حوالہ جات کی ایک تخصص ہے بیرونی لنکس ایک انٹرایکٹو مثال مشترکہ الگورتھم بے ترتیب الگورتھم ترتیبات مونٹی کارلو طریقوں کے مضامین مثال کے ساتھ چھدم کوڈ مضامین مثال کے طور پر ازگر (پروگرامنگ زبان) کوڈ کے ساتھ