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 એ [i] અને [j] નું વિનિમય કરે ઉદાહરણો પેન્સિલ-એન્ડ-પેપર પદ્ધતિ આ ઉદાહરણ ફિશર અને યેટ્સની મૂળ પદ્ધતિનો ઉપયોગ કરીને A થી H સુધીના અક્ષરોને ક્રમબદ્ધ કરે છે. ઉદાહરણ તરીકે, જો જે = 3 હોય, તો પછી કોઈ વ્યક્તિ સ્ક્રેચ પેડ પર ત્રીજો અક્ષર બહાર કાઢે છે અને તેને પરિણામે લખે છેઃ બીજી રેન્ડમ સંખ્યા પસંદ કરવામાં આવે છે, આ વખતે 1 થી 7 સુધી. જો સંખ્યા 4 હોય, તો પછી કોઈ ચોથો અક્ષર બહાર કાઢે છે જે હજુ સુધી સ્ક્રેચ પેડ પર અથડાયો નથી અને તેને પરિણામમાં ઉમેરે છેઃ આગામી રેન્ડમ નંબર 1 થી 6 સુધી પસંદ કરવામાં આવે છે, અને પછી 1 થી 5 સુધી, અને તેથી વધુ, હંમેશા ઉપરની જેમ સ્ટ્રાઇક-આઉટ પ્રક્રિયાને પુનરાવર્તન કરે છેઃ આધુનિક પદ્ધતિ ડર્સ્ટનફેલ્ડના અલ્ગોરિધમના સંસ્કરણમાં, પસંદ કરેલા અક્ષરોને બહાર કાઢવાને બદલે અને તેમને અન્યત્ર નકલ કરવાને બદલે, તેઓ હજુ સુધી પસંદ ન કરેલા છેલ્લા અક્ષર સાથે અદલાબદલી કરવામાં આવે છે. પહેલાની જેમ A થી H સુધીના અક્ષરોથી શરૂ કરીનેઃ 1 થી 8 સુધીની રેન્ડમ સંખ્યા j પસંદ કરો, અને પછી jth અને 8મા અક્ષરોની અદલાબદલી કરો. તેથી, જો રેન્ડમ નંબર 6 હોય, ઉદાહરણ તરીકે, સૂચિમાં છઠ્ઠા અને આઠમા અક્ષરોને બદલોઃ આગામી રેન્ડમ નંબર 1 થી 7 સુધી પસંદ કરવામાં આવે છે, અને પસંદ કરેલ અક્ષરને 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 ≤ જે ≤ i જો જે ≤ i એ [i] એ [જે] એ [જે] એ [જે] એ સ્રોત [i] ઇનસાઇડ-આઉટ શફલ ઇન્ડક્શન દ્વારા સાચું હોવાનું જોઈ શકાય છે. એક સંપૂર્ણ રેન્ડમ નંબર જનરેટર ધારીએ તો, દરેક n! રેન્ડમ સંખ્યાઓના વિવિધ ક્રમ કે જે રેન્ડમના કોલમાંથી મેળવી શકાય છે તે મૂલ્યોના અલગ ક્રમચય પેદા કરશે, તેથી આ બધા બરાબર એક જ વાર મેળવવામાં આવે છે. એવી શરત કે જે તપાસ કરે છે કે જે § 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 માં, રેન્ડમ નંબર જે ની શ્રેણીમાંથી પસંદ કરવામાં આવે છે. આ સરળ ફેરફાર અલ્ગોરિધમમાં ફેરફાર કરે છે જેથી પરિણામી ક્રમચયમાં હંમેશા એક જ ચક્ર હોય. હકીકતમાં, નીચે વર્ણવ્યા મુજબ, જ્યારે સામાન્ય ફિશર-યેટ્સ શફલનો હેતુ હોય ત્યારે આકસ્મિક રીતે સત્તોલોના અલ્ગોરિધમનો અમલ કરવો ખૂબ જ સરળ છે. આ (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) માટે પરવાનગી આપે છે! ચક્ર સંકેતનાં અન્ય સ્થાનોને ભરવા માટે બાકીના મૂલ્યોના ક્રમચયો. પાયથોનમાં સત્તોલોના અલ્ગોરિધમનો નમૂનો અમલીકરણ છેઃ રેન્ડમ ઇમ્પોર્ટ રેન્ડરેંજ ડેફ સત્તોલો _ સાયકલ (આઇટમ્સ)-> કંઈ નહીં માંથીઃ "સત્તોલોના અલ્ગોરિધમ". i = લેન (વસ્તુઓ) જ્યારે i> 1: i = i-1j = રેન્ડ્રેન્જ (i) #0 <= j <= i-1 વસ્તુઓ [j], વસ્તુઓ [i] = વસ્તુઓ [i], વસ્તુઓ [j] અન્ય ફેરબદલ અલ્ગોરિધમ્સ સાથે સરખામણી ફિશર-યેટ્સ ફેરબદલની એસિમ્પ્ટોટિક સમય અને જગ્યા જટિલતા શ્રેષ્ઠ છે. ઉચ્ચ ગુણવત્તાના નિષ્પક્ષ રેન્ડમ નંબર સ્રોત સાથે જોડાઈને, તે નિષ્પક્ષ પરિણામો ઉત્પન્ન કરવાની ખાતરી પણ આપે છે. કેટલાક અન્ય ઉકેલોની તુલનામાં, તેનો ફાયદો એ પણ છે કે, જો પરિણામી ક્રમચયોના માત્ર એક ભાગની જરૂર હોય, તો તેને અડધો રસ્તો રોકી શકાય છે, અથવા તો રોકી શકાય છે અને વારંવાર પુનઃપ્રારંભ કરી શકાય છે, જરૂરિયાત મુજબ ક્રમચયો ઉત્પન્ન કરી શકાય છે. નિષ્કપટ પદ્ધતિ તમામ ઘટકોમાંથી અવ્યવસ્થિત રીતે પસંદ કરેલા અન્ય તત્વ સાથે દરેક તત્વની અદલાબદલી કરવાની નિષ્કપટ પદ્ધતિ પક્ષપાતી છે. જુદા જુદા ક્રમચયોમાં પેદા થવાની જુદી જુદી સંભાવનાઓ હશે, દરેક માટે, કારણ કે વિવિધ ક્રમચયોની સંખ્યા, અલ્ગોરિધમનોના યાદૃચ્છિક પરિણામોની સંખ્યાને સમાનરૂપે વિભાજિત કરતી નથી. ખાસ કરીને, બર્ટ્રાન્ડની ધારણા અનુસાર અને વચ્ચે ઓછામાં ઓછી એક મુખ્ય સંખ્યા હશે, અને આ સંખ્યા ભાગશે પણ ભાગશે નહીં. રેન્ડમ ઇમ્પોર્ટમાંથી રેન્ડરેંજ ડેફ નાઇવ _ શફલ (વસ્તુઓ)-> કંઈ નહિંઃ "" એક નિષ્કપટ પદ્ધતિ. શું ન કરવું તેનું આ એક ઉદાહરણ છે-તેના બદલે ફિશર-યેટ્સનો ઉપયોગ કરો. શ્રેણી (n) માં i માટે n = લેન (આઇટમ્સ): j = રેન્ડ્રેન્જ (n) #0 <= j <= n-1 આઇટમ્સ [j], આઇટમ્સ [i] = આઇટમ્સ [i], આઇટમ્સ [j] સૉર્ટિંગ એક વૈકલ્પિક પદ્ધતિ સમૂહના દરેક ઘટકને અવ્યવસ્થિત સંખ્યા સોંપે છે અને પછી સોંપેલ સંખ્યાઓ અનુસાર સમૂહને સૉર્ટ કરે છે. સૉર્ટિંગ પદ્ધતિમાં ફિશર-યેટ્સ જેવી જ એસિમ્પ્ટોટિક સમય જટિલતા છેઃ સામાન્ય સૉર્ટિંગ ઓ (એન લોગ એન) હોવા છતાં, ઓ (એન) સમયમાં રેડિક્સ સૉર્ટનો ઉપયોગ કરીને સંખ્યાઓને અસરકારક રીતે સૉર્ટ કરવામાં આવે છે. ફિશર-યેટ્સ શફલની જેમ, સૉર્ટિંગ પદ્ધતિ નિષ્પક્ષ પરિણામો ઉત્પન્ન કરે છે. જો કે, સોંપેલ રેન્ડમ સંખ્યાઓ ક્યારેય ડુપ્લિકેટ ન થાય તેની ખાતરી કરવા માટે કાળજી લેવી આવશ્યક છે, કારણ કે સૉર્ટિંગ અલ્ગોરિધમ્સ સામાન્ય રીતે ટાઈના કિસ્સામાં તત્વોને રેન્ડમલી ઓર્ડર કરતા નથી. વધુમાં, આ પદ્ધતિ માટે એસિમ્પ્ટોટિકલી મોટી જગ્યાની જરૂર છેઃ ઓ (એન) રેન્ડમ સંખ્યાઓ માટે વધારાની સંગ્રહ જગ્યા, વિરુદ્ધ ફિશર-યેટ્સ શફલ માટે ઓ (1) જગ્યા. છેવટે, સૉર્ટિંગ પદ્ધતિમાં સરળ સમાંતર અમલીકરણ છે, જે ફિશર-યેટ્સ શફલથી વિપરીત છે, જે ક્રમિક છે. ઉપરોક્ત પદ્ધતિનો એક પ્રકાર કે જેણે વપરાશકર્તા-નિર્દિષ્ટ સરખામણી કાર્યો સાથે સૉર્ટિંગને ટેકો આપતી ભાષાઓમાં થોડો ઉપયોગ જોયો છે તે છે સૂચિને તુલનાત્મક કાર્ય સાથે સૉર્ટ કરીને ફેરબદલ કરવી જે રેન્ડમ મૂલ્યો આપે છે. જો કે, આ ખૂબ જ બિન-સમાન વિતરણો ઉત્પન્ન કરે તેવી શક્યતા છે, જે વધુમાં ઉપયોગમાં લેવાતા સૉર્ટિંગ અલ્ગોરિધમ પર ભારે આધાર રાખે છે. દાખલા તરીકે ધારો કે ક્વિકસોર્ટનો ઉપયોગ સૉર્ટિંગ અલ્ગોરિધમ તરીકે થાય છે, જેમાં પ્રથમ પાઇવોટ એલિમેન્ટ તરીકે પસંદ કરેલ નિશ્ચિત એલિમેન્ટ છે. અલ્ગોરિધમ અન્ય તમામ ઘટકો સાથે ધરીની સરખામણી કરવાનું શરૂ કરે છે જેથી તેમને તે ઓછા અને તેના કરતા મોટા ભાગમાં અલગ કરી શકાય, અને તે જૂથોના સંબંધિત કદ ધરી તત્વનું અંતિમ સ્થાન નક્કી કરશે. સમાન રીતે વિતરિત યાદૃચ્છિક ક્રમચયો માટે, દરેક સંભવિત અંતિમ સ્થિતિ ધરી તત્વ માટે સમાન રીતે સંભવિત હોવી જોઈએ, પરંતુ જો દરેક પ્રારંભિક સરખામણી સમાન સંભાવના સાથે "ઓછી" અથવા "મોટી" વળતર આપે છે, તો તે સ્થિતિમાં p = 1/2 માટે દ્વિપદી વિતરણ હશે, જે અંતની નજીકની સ્થિતિ કરતાં ઘણી વધારે સંભાવના સાથે ક્રમની મધ્યની નજીકની સ્થિતિ આપે છે. મર્જ સૉર્ટ જેવી અન્ય સૉર્ટિંગ પદ્ધતિઓ પર લાગુ કરાયેલ રેન્ડમાઇઝ્ડ કમ્પેરીઝન ફંક્શન્સ એવા પરિણામો ઉત્પન્ન કરી શકે છે જે વધુ સમાન દેખાય છે, પરંતુ તે પણ તદ્દન નથી, કારણ કે બે સિક્વન્સને વારંવાર તેમાંથી એકને સમાન સંભાવના સાથે પસંદ કરીને મર્જ કરવાથી (જ્યાં સુધી પસંદગી એક સિક્વન્સના થાકને કારણે ફરજ પાડવામાં ન આવે ત્યાં સુધી) સમાન વિતરણ સાથે પરિણામો ઉત્પન્ન થતું નથી; તેના બદલે સિક્વન્સ પસંદ કરવાની સંભાવના તેમાં બાકી રહેલા તત્વોની સંખ્યાના પ્રમાણમાં હોવી જોઈએ. હકીકતમાં કોઈ પણ પદ્ધતિ કે જે સમાન સંભાવના ("સિક્કો પલટી") સાથે માત્ર બે-તરફી રેન્ડમ ઘટનાઓનો ઉપયોગ કરે છે, મર્યાદિત સંખ્યામાં પુનરાવર્તિત થાય છે, તે એક સમાન વિતરણ સાથે ક્રમ (બેથી વધુ તત્વોના) ના ક્રમચયો પેદા કરી શકે છે, કારણ કે દરેક એક્ઝેક્યુશન પાથમાં સંભાવના તરીકે 2 ની ઘાત સાથે પરિમાણીય સંખ્યા હશે, જ્યારે જરૂરી સંભાવના 1/n હશે! દરેક સંભવિત ક્રમચય તે સ્વરૂપનું નથી. સૈદ્ધાંતિક રીતે આ ફેરબદલ પદ્ધતિ પ્રોગ્રામની નિષ્ફળતામાં પરિણમી શકે છે જેમ કે અનંત લૂપ્સ અથવા ઍક્સેસ ઉલ્લંઘન, કારણ કે સૉર્ટિંગ અલ્ગોરિધમનો સચોટતા ઓર્ડર સંબંધ (જેમ કે સંક્રમણ) ના ગુણધર્મો પર આધારિત હોઈ શકે છે જે રેન્ડમ મૂલ્યો ઉત્પન્ન કરતી સરખામણીમાં ચોક્કસપણે નહીં હોય. જ્યારે આ પ્રકારની વર્તણૂક સૉર્ટિંગ દિનચર્યાઓ સાથે થવી જોઈએ નહીં જે ક્યારેય એવી સરખામણી કરતી નથી કે જેના પરિણામની નિશ્ચિતતા સાથે આગાહી કરી શકાય (અગાઉની સરખામણીઓના આધારે), ઇરાદાપૂર્વક આવી તુલના કરવા માટે માન્ય કારણો હોઈ શકે છે. દાખલા તરીકે, હકીકત એ છે કે કોઈપણ તત્વની પોતાની સમાન સરખામણી થવી જોઈએ, તે કાર્યક્ષમતાના કારણોસર તેમને પ્રહરી મૂલ્ય તરીકે ઉપયોગમાં લેવાની મંજૂરી આપે છે, અને જો આ કિસ્સો હોય, તો રેન્ડમ સરખામણી કાર્ય સૉર્ટિંગ અલ્ગોરિધમને તોડી નાખશે. ફિશર-યેટ્સ શફલનો અમલ કરતી વખતે પૂર્વગ્રહના સંભવિત સ્રોતોની કાળજી લેવી આવશ્યક છે, બંને અલ્ગોરિધમનો અમલ કરતી વખતે અને તેના પર બનેલી રેન્ડમ સંખ્યાઓની પેઢીમાં, અન્યથા પરિણામો શોધી શકાય તેવા પૂર્વગ્રહ દર્શાવી શકે છે. પૂર્વગ્રહના સંખ્યાબંધ સામાન્ય સ્રોતો નીચે સૂચિબદ્ધ કરવામાં આવ્યા છે. અમલીકરણ ભૂલો ફિશર-યેટ્સ ફેરબદલનો અમલ કરતી વખતે એક સામાન્ય ભૂલ એ છે કે ખોટી શ્રેણીમાંથી રેન્ડમ સંખ્યાઓ પસંદ કરવી. ખામીયુક્ત અલ્ગોરિધમ યોગ્ય રીતે કામ કરતું હોય તેવું લાગી શકે છે, પરંતુ તે સમાન સંભાવના સાથે દરેક સંભવિત ક્રમચયો પેદા કરશે નહીં, અને તે ચોક્કસ ક્રમચયો પેદા કરી શકશે નહીં. ઉદાહરણ તરીકે, એક સામાન્ય ઓફ-બાય-વન ભૂલ એ હશે કે ઉપરના ઉદાહરણમાં અદલાબદલી કરવા માટે એન્ટ્રીની અનુક્રમણિકા જે પસંદ કરવી તે હંમેશા એન્ટ્રીની અનુક્રમણિકા i કરતા સખત રીતે ઓછી હશે જેની સાથે તેને અદલાબદલી કરવામાં આવશે. આ ફિશર-યેટ્સ શફલને સત્તોલોના અલ્ગોરિધમમાં ફેરવે છે, જે તમામ તત્વોને સંડોવતા એક જ ચક્ર ધરાવતા માત્ર ક્રમચયો ઉત્પન્ન કરે છેઃ ખાસ કરીને, આ ફેરફાર સાથે, એરેનું કોઈ પણ તત્વ ક્યારેય તેની મૂળ સ્થિતિમાં સમાપ્ત થઈ શકતું નથી. એ જ રીતે, હંમેશા દરેક પુનરાવર્તન પર માન્ય એરે સૂચકાંકોની સમગ્ર શ્રેણીમાંથી જે પસંદ કરવાથી પણ એવું પરિણામ મળે છે જે પક્ષપાતી હોય છે, જોકે દેખીતી રીતે તે ઓછું છે. આ એ હકીકત પરથી જોઈ શકાય છે કે આમ કરવાથી અદલાબદલીના અલગ સંભવિત ક્રમ મળે છે, જ્યારે કે ત્યાં માત્ર 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 ને સમાનરૂપે વિભાજિત કરતું નથીઃ 16 નો 100 કરતા ઓછો અથવા બરાબરનો સૌથી મોટો ગુણાંક 6 × 16 = 96 છે, અને તે અપૂર્ણ શ્રેણી 96-99 માંની સંખ્યાઓ છે જે પૂર્વગ્રહનું કારણ બને છે. સમસ્યાને ઉકેલવાનો સૌથી સરળ રસ્તો એ છે કે બાકીની સંખ્યા લેતા પહેલા તે સંખ્યાઓને કાઢી નાખવી અને યોગ્ય શ્રેણીમાં સંખ્યા ન આવે ત્યાં સુધી ફરીથી પ્રયાસ કરવાનું ચાલુ રાખવું. જ્યારે સૈદ્ધાંતિક રીતે આ, સૌથી ખરાબ કિસ્સામાં, કાયમ માટે લાગી શકે છે, ફરીથી પ્રયાસોની અપેક્ષિત સંખ્યા હંમેશા એક કરતા ઓછી હશે. એક સંબંધિત સમસ્યા અમલીકરણ સાથે થાય છે જે પહેલા રેન્ડમ ફ્લોટિંગ-પોઇન્ટ નંબર પેદા કરે છે-સામાન્ય રીતે શ્રેણીમાં [0,1]-અને પછી તેને ઇચ્છિત શ્રેણીના કદથી ગુણાકાર કરો અને નીચે ગોળાકાર કરો. અહીં સમસ્યા એ છે કે રેન્ડમ ફ્લોટિંગ-પોઇન્ટ નંબરો, જો કે કાળજીપૂર્વક ઉત્પન્ન થાય છે, હંમેશા માત્ર મર્યાદિત ચોકસાઇ ધરાવે છે. આનો અર્થ એ છે કે કોઈપણ શ્રેણીમાં સંભવિત ફ્લોટિંગ પોઇન્ટ મૂલ્યોની માત્ર મર્યાદિત સંખ્યા હોય છે, અને જો શ્રેણીને સંખ્યાબંધ વિભાગોમાં વહેંચવામાં આવે છે જે આ સંખ્યાને સમાનરૂપે વિભાજિત કરતી નથી, તો કેટલાક વિભાગો અન્ય કરતા વધુ સંભવિત મૂલ્યો સાથે સમાપ્ત થશે. જ્યારે પરિણામી પૂર્વગ્રહ અગાઉના કેસની જેમ સમાન વ્યવસ્થિત નીચે તરફનું વલણ બતાવશે નહીં, તે હજુ પણ ત્યાં જ રહેશે. સ્યુડોરાન્ડમ જનરેટર વધારાની સમસ્યા ત્યારે ઊભી થાય છે જ્યારે ફિશર-યેટ્સ શફલનો ઉપયોગ સ્યુડોરાન્ડમ નંબર જનરેટર અથવા પી. આર. એન. જી. સાથે કરવામાં આવે છેઃ કારણ કે આવા જનરેટર દ્વારા સંખ્યાઓના ઉત્પાદનનો ક્રમ સંપૂર્ણપણે ક્રમની શરૂઆતમાં તેની આંતરિક સ્થિતિ દ્વારા નક્કી કરવામાં આવે છે, આવા જનરેટર દ્વારા સંચાલિત શફલ સંભવતઃ જનરેટરની અલગ સંભવિત સ્થિતિઓ કરતાં વધુ અલગ ક્રમચયો પેદા કરી શકતું નથી. જ્યારે સંભવિત સ્થિતિઓની સંખ્યા ક્રમચયોની સંખ્યા કરતાં વધી જાય ત્યારે પણ, સંખ્યાઓના ક્રમથી ક્રમચયો સુધીના નકશાની અનિયમિત પ્રકૃતિનો અર્થ એ છે કે કેટલાક ક્રમચયો અન્ય કરતા વધુ વખત થશે. આમ, પૂર્વગ્રહને ઘટાડવા માટે, પી. આર. એન. જી. ની સ્થિતિઓની સંખ્યા પરિમાણના ઓછામાં ઓછા કેટલાક ક્રમ દ્વારા ક્રમચયોની સંખ્યા કરતાં વધી જવી જોઈએ. ઉદાહરણ તરીકે, ઘણી પ્રોગ્રામિંગ ભાષાઓ અને/અથવા પુસ્તકાલયો દ્વારા પ્રદાન કરાયેલ બિલ્ટ-ઇન સ્યુડોરાન્ડમ નંબર જનરેટરમાં ઘણીવાર આંતરિક સ્થિતિના માત્ર 32 બિટ્સ હોઈ શકે છે, જેનો અર્થ છે કે તે માત્ર સંખ્યાઓના 232 વિવિધ ક્રમ પેદા કરી શકે છે. જો આવા જનરેટરનો ઉપયોગ 52 કાર્ડ્સના ડેકને ફેરબદલ કરવા માટે કરવામાં આવે, તો તે 52 કાર્ડ્સનો માત્ર એક નાનો ભાગ જ પેદા કરી શકે છે! ≈ 2225.6 સંભવિત ક્રમચયો. 226 બિટ્સથી ઓછી આંતરિક સ્થિતિ ધરાવતા જનરેટર માટે 52-કાર્ડ ડેકના તમામ સંભવિત ક્રમચયો પેદા કરવા અશક્ય છે. કોઈ સ્યુડોરાન્ડમ નંબર જનરેટર વધુ અલગ ક્રમ પેદા કરી શકતું નથી, પ્રારંભિકતાના બિંદુથી શરૂ કરીને, ત્યાં અલગ બીજ મૂલ્યો છે જેની સાથે તેને પ્રારંભિક કરી શકાય છે. આમ, એક જનરેટર કે જે 1024 બિટ્સની આંતરિક સ્થિતિ ધરાવે છે પરંતુ જે 32-બીટ બીજ સાથે પ્રારંભ કરવામાં આવે છે તે હજુ પણ પ્રારંભ પછી તરત જ 232 વિવિધ ક્રમચયો ઉત્પન્ન કરી શકે છે. જો કોઈ વ્યક્તિ ક્રમચયો પેદા કરવા માટે તેનો ઉપયોગ શરૂ કરતા પહેલા જનરેટરનો ઘણી વખત ઉપયોગ કરે તો તે વધુ ક્રમચયો પેદા કરી શકે છે, પરંતુ આ અવ્યવસ્થિતતા વધારવાની ખૂબ જ બિનકાર્યક્ષમ રીત છેઃ ધારો કે કોઈ જનરેટરનો એક અબજ સુધીની યાદૃચ્છિક સંખ્યાનો ઉપયોગ કરવાની વ્યવસ્થા કરી શકે છે, સરળતા માટે 230 કહો, પ્રારંભ અને ક્રમચયો પેદા કરવા વચ્ચેનો સમય, તો સંભવિત ક્રમચયોની સંખ્યા હજુ પણ માત્ર 262 છે. વધુ એક સમસ્યા ત્યારે ઊભી થાય છે જ્યારે ઉપર વર્ણવેલ રેન્જ રિડક્શનની ડિવાઇડ-એન્ડ-ટેક-રિમેઇન્ડર પદ્ધતિ સાથે સરળ રેખીય એકરૂપ PRNG નો ઉપયોગ કરવામાં આવે છે. અહીં સમસ્યા એ છે કે મોડ્યુલો 2e સાથે રેખીય એકરૂપ PRNG ના નીચા ક્રમના બિટ્સ ઉચ્ચ ક્રમના બિટ્સ કરતા ઓછા અવ્યવસ્થિત હોય છેઃ જનરેટરના નીચા n બિટ્સનો સમયગાળો મહત્તમ 2n હોય છે. જ્યારે વિભાજક બેની શક્તિ હોય, ત્યારે બાકીનો ભાગ લેવાનો અર્થ અનિવાર્યપણે ઉચ્ચ ક્રમના બિટ્સને દૂર ફેંકવાનો થાય છે, જેમ કે એક નોંધપાત્ર રીતે ઓછા યાદૃચ્છિક મૂલ્ય સાથે સમાપ્ત થાય છે. જો એલ. સી. જી. માં મુખ્ય મોડ્યુલો હોય તો જુદા જુદા નિયમો લાગુ પડે છે, પરંતુ આવા જનરેટર અસામાન્ય છે. આ સામાન્ય નિયમનું એક ઉદાહરણ છે કે નબળી ગુણવત્તાની આર. એન. જી. અથવા પી. આર. એન. જી. નબળી ગુણવત્તાની ફેરબદલ પેદા કરશે. આર. સી. 4 પણ જુઓ, જે એરે રિઝર્વોઇર સેમ્પલિંગને ફેરબદલ કરવા પર આધારિત સ્ટ્રીમ સાઇફર છે, ખાસ કરીને એલ્ગોરિધમ આર જે ફિશર-યેટ્સ શફલ સંદર્ભોની વિશેષતા છે બાહ્ય કડીઓ એક ઇન્ટરેક્ટિવ ઉદાહરણ સંયોજન એલ્ગોરિધમ્સ રેન્ડમાઇઝ્ડ એલ્ગોરિધમ્સ ક્રમચયો મોન્ટે કાર્લો પદ્ધતિઓ ઉદાહરણ સ્યુડોકોડ સાથે લેખો ઉદાહરણ તરીકે પાયથોન (પ્રોગ્રામિંગ લેંગ્વેજ) કોડ સાથેના લેખો