Fisher–Yates shuffle
ಫಿಶರ್-ಯೇಟ್ಸ್ ಷಫಲ್ ಒಂದು ಸೀಮಿತ ಅನುಕ್ರಮವನ್ನು ಷಫಲ್ ಮಾಡುವ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಅಲ್ಗಾರಿದಮ್ ಅನುಕ್ರಮದ ಎಲ್ಲಾ ಅಂಶಗಳ ಪಟ್ಟಿಯನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಮತ್ತು ಯಾವುದೇ ಅಂಶಗಳು ಉಳಿದಿರದವರೆಗೂ ಪಟ್ಟಿಯಿಂದ ಒಂದು ಅಂಶವನ್ನು ಯಾದೃಚ್ಛಿಕವಾಗಿ ಎಳೆಯುವ ಮೂಲಕ ಷಫಲ್ ಅನುಕ್ರಮದಲ್ಲಿ ಮುಂದಿನ ಅಂಶವನ್ನು ನಿರಂತರವಾಗಿ ನಿರ್ಧರಿಸುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ ಪಕ್ಷಪಾತವಿಲ್ಲದ ಕ್ರಮಪಲ್ಲಟನೆಯನ್ನು ಉಂಟುಮಾಡುತ್ತದೆಃ ಪ್ರತಿ ಕ್ರಮಪಲ್ಲಟನೆಯು ಸಮಾನವಾಗಿ ಸಂಭವಿಸುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ನ ಆಧುನಿಕ ಆವೃತ್ತಿಯು ವಸ್ತುಗಳ ಸಂಖ್ಯೆಗೆ ಅನುಗುಣವಾಗಿ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಮತ್ತು ಅವುಗಳನ್ನು ಸ್ಥಳದಲ್ಲಿ ಬದಲಾಯಿಸುತ್ತದೆ. ಫಿಶರ್-ಯೇಟ್ಸ್ ಷಫಲ್ಗೆ ಇದನ್ನು ಮೊದಲು ವಿವರಿಸಿದ ರೊನಾಲ್ಡ್ ಫಿಶರ್ ಮತ್ತು ಫ್ರಾಂಕ್ ಯೇಟ್ಸ್ ಅವರ ಹೆಸರನ್ನು ಇಡಲಾಗಿದೆ ಮತ್ತು ಇದನ್ನು ಡೊನಾಲ್ಡ್ ಕ್ನುತ್ ನಂತರ ಕ್ನುತ್ ಷಫಲ್ ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ. ಸಟ್ಟೋಲೋಸ್ ಅಲ್ಗಾರಿದಮ್ ಎಂದು ಕರೆಯಲ್ಪಡುವ ಫಿಶರ್-ಯೇಟ್ಸ್ ಷಫಲ್ನ ಒಂದು ರೂಪಾಂತರವನ್ನು ಯಾದೃಚ್ಛಿಕ ಕ್ರಮಪಲ್ಲಟನೆಗಳ ಬದಲಿಗೆ n ಉದ್ದದ ಯಾದೃಚ್ಛಿಕ ಆವರ್ತಕ ಕ್ರಮಪಲ್ಲಟನೆಗಳನ್ನು ಉತ್ಪಾದಿಸಲು ಬಳಸಬಹುದು. ಫಿಶರ್ ಮತ್ತು ಯೇಟ್ಸ್ ಅವರ ಮೂಲ ವಿಧಾನವಾದ ದಿ ಫಿಶರ್-ಯೇಟ್ಸ್ ಷಫಲ್ ಅನ್ನು ಅದರ ಮೂಲ ರೂಪದಲ್ಲಿ 1938 ರಲ್ಲಿ ರೊನಾಲ್ಡ್ ಫಿಶರ್ ಮತ್ತು ಫ್ರಾಂಕ್ ಯೇಟ್ಸ್ ಅವರು ತಮ್ಮ ಪುಸ್ತಕ ಸ್ಟ್ಯಾಟಿಸ್ಟಿಕಲ್ ಕೋಷ್ಟಕಗಳು ಫಾರ್ ಬಯೋಲಾಜಿಕಲ್, ಅಗ್ರಿಕಲ್ಚರಲ್ ಮತ್ತು ಮೆಡಿಕಲ್ ರಿಸರ್ಚ್ ನಲ್ಲಿ ವಿವರಿಸಿದ್ದಾರೆ. ಅಲ್ಗಾರಿದಮ್ನ ಅವರ ವಿವರಣೆಯು ಪೆನ್ಸಿಲ್ ಮತ್ತು ಕಾಗದವನ್ನು ಬಳಸಿತು; ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆಗಳ ಕೋಷ್ಟಕವು ಯಾದೃಚ್ಛಿಕತೆಯನ್ನು ಒದಗಿಸಿತು. 1ರಿಂದ Nರವರೆಗಿನ ಸಂಖ್ಯೆಗಳ ಯಾದೃಚ್ಛಿಕ ಕ್ರಮಪಲ್ಲಟನೆಯನ್ನು ಉತ್ಪಾದಿಸಲು ನೀಡಲಾದ ಮೂಲ ವಿಧಾನವು ಈ ಕೆಳಗಿನಂತೆ ಹೋಗುತ್ತದೆಃ 1ರಿಂದ Nರವರೆಗಿನ ಸಂಖ್ಯೆಗಳನ್ನು ಬರೆಯಿರಿ. ಒಂದು ಮತ್ತು ಉಳಿದಿರುವ (ಅಂತರ್ಗತ) ಅಸಂಖ್ಯಾತ ಸಂಖ್ಯೆಗಳ ನಡುವಿನ ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆಯಾದ k ಅನ್ನು ಆರಿಸಿಕೊಳ್ಳಿ. ಕೆಳ ತುದಿಯಿಂದ ಎಣಿಸಿದಾಗ, ಇನ್ನೂ ಹೊರಬರದ kth ಸಂಖ್ಯೆಯನ್ನು ಹೊಡೆದು, ಅದನ್ನು ಪ್ರತ್ಯೇಕ ಪಟ್ಟಿಯ ಕೊನೆಯಲ್ಲಿ ಬರೆಯಿರಿ. ಎಲ್ಲಾ ಸಂಖ್ಯೆಗಳು ಮುಗಿಯುವವರೆಗೆ 2ನೇ ಹಂತದಿಂದ ಪುನರಾವರ್ತಿಸಿ. 3ನೇ ಹಂತದಲ್ಲಿ ಬರೆಯಲಾದ ಸಂಖ್ಯೆಗಳ ಅನುಕ್ರಮವು ಈಗ ಮೂಲ ಸಂಖ್ಯೆಗಳ ಯಾದೃಚ್ಛಿಕ ಕ್ರಮಪಲ್ಲಟನೆಯಾಗಿದೆ. ಮೇಲಿನ ಹಂತ 2 ರಲ್ಲಿ ಆಯ್ಕೆ ಮಾಡಲಾದ ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆಗಳು ನಿಜವಾಗಿಯೂ ಯಾದೃಚ್ಛಿಕ ಮತ್ತು ಪಕ್ಷಪಾತರಹಿತವಾಗಿವೆ, ಆದ್ದರಿಂದ ಫಲಿತಾಂಶದ ಕ್ರಮಪಲ್ಲಟನೆಯೂ ಆಗಿರುತ್ತದೆ. ಯಾವುದೇ ಪಕ್ಷಪಾತವನ್ನು ತಪ್ಪಿಸುವ ರೀತಿಯಲ್ಲಿ ಸರಬರಾಜು ಮಾಡಿದ ಕೋಷ್ಟಕಗಳಿಂದ ಯಾವುದೇ ಅಪೇಕ್ಷಿತ ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ಅಂತಹ ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆಗಳನ್ನು ಹೇಗೆ ಪಡೆಯುವುದು ಎಂಬುದನ್ನು ವಿವರಿಸಲು ಫಿಶರ್ ಮತ್ತು ಯೇಟ್ಸ್ ಕಾಳಜಿ ವಹಿಸಿದರು. ಅವರು ಸರಳವಾದ ವಿಧಾನವನ್ನು ಬಳಸುವ ಸಾಧ್ಯತೆಯನ್ನು ಸಹ ಸೂಚಿಸಿದರು-ಒಂದರಿಂದ ಎನ್ಗೆ ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆಗಳನ್ನು ಆರಿಸುವುದು ಮತ್ತು ಯಾವುದೇ ನಕಲುಗಳನ್ನು ತ್ಯಜಿಸುವುದು-ಕ್ರಮಪಲ್ಲಟನೆಯ ಮೊದಲಾರ್ಧವನ್ನು ಉತ್ಪಾದಿಸಲು, ಮತ್ತು ಉಳಿದ ಅರ್ಧಕ್ಕೆ ಹೆಚ್ಚು ಸಂಕೀರ್ಣವಾದ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಮಾತ್ರ ಅನ್ವಯಿಸುತ್ತದೆ, ಅಲ್ಲಿ ನಕಲು ಸಂಖ್ಯೆಯನ್ನು ಆಯ್ಕೆ ಮಾಡುವುದು ನಿರಾಶಾದಾಯಕವಾಗಿ ಸಾಮಾನ್ಯವಾಗುತ್ತದೆ. ಆಧುನಿಕ ಅಲ್ಗಾರಿದಮ್ ಕಂಪ್ಯೂಟರ್ ಬಳಕೆಗಾಗಿ ವಿನ್ಯಾಸಗೊಳಿಸಲಾದ ಫಿಶರ್-ಯೇಟ್ಸ್ ಷಫಲ್ನ ಆಧುನಿಕ ಆವೃತ್ತಿಯನ್ನು 1964 ರಲ್ಲಿ ರಿಚರ್ಡ್ ಡರ್ಸ್ಟೆನ್ಫೆಲ್ಡ್ ಪರಿಚಯಿಸಿದರು ಮತ್ತು ದಿ ಆರ್ಟ್ ಆಫ್ ಕಂಪ್ಯೂಟರ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ನಲ್ಲಿ ಡೊನಾಲ್ಡ್ ಇ. ಕ್ನುಥ್ ಅವರು "ಅಲ್ಗಾರಿದಮ್ ಪಿ (ಷಫ್ಲಿಂಗ್)" ಎಂದು ಜನಪ್ರಿಯಗೊಳಿಸಿದರು. ಡರ್ಸ್ಟನ್ಫೆಲ್ಡ್ರ ಲೇಖನವಾಗಲೀ ಅಥವಾ ಕ್ನತ್ನ ದಿ ಆರ್ಟ್ ಆಫ್ ಕಂಪ್ಯೂಟರ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ನ ಮೊದಲ ಆವೃತ್ತಿಯಾಗಲೀ ಫಿಶರ್ ಮತ್ತು ಯೇಟ್ಸ್ ಅವರ ಕೆಲಸವನ್ನು ಒಪ್ಪಿಕೊಂಡಿಲ್ಲ; ಅವರಿಗೆ ಅದರ ಬಗ್ಗೆ ತಿಳಿದಿಲ್ಲದಿರಬಹುದು. ಕ್ನುಥ್ ಅವರ ದಿ ಆರ್ಟ್ ಆಫ್ ಕಂಪ್ಯೂಟರ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ನ ನಂತರದ ಆವೃತ್ತಿಗಳು ಫಿಶರ್ ಮತ್ತು ಯೇಟ್ಸ್ ಅವರ ಕೊಡುಗೆಯನ್ನು ಉಲ್ಲೇಖಿಸುತ್ತವೆ. ಡರ್ಸ್ಟನ್ಫೆಲ್ಡ್ ವಿವರಿಸಿದ ಅಲ್ಗಾರಿದಮ್ ಫಿಶರ್ ಮತ್ತು ಯೇಟ್ಸ್ ನೀಡಿದ ಅಲ್ಗಾರಿದಮ್ಗಿಂತ ಹೆಚ್ಚು ಪರಿಣಾಮಕಾರಿಯಾಗಿದೆಃ ಆದರೆ ಫಿಶರ್ ಮತ್ತು ಯೇಟ್ಸ್ ವಿಧಾನದ ನಿಷ್ಕಪಟ ಕಂಪ್ಯೂಟರ್ ಅನುಷ್ಠಾನವು ಮೇಲಿನ ಹಂತ 3 ರಲ್ಲಿ ಉಳಿದ ಸಂಖ್ಯೆಗಳನ್ನು ಎಣಿಸಲು ಅನಗತ್ಯ ಸಮಯವನ್ನು ಕಳೆಯುತ್ತದೆ, ಡರ್ಸ್ಟನ್ಫೆಲ್ಡ್ನ ಪರಿಹಾರವೆಂದರೆ "ಹೊಡೆದ" ಸಂಖ್ಯೆಗಳನ್ನು ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯಲ್ಲಿ ಕೊನೆಯ ಅನಿರ್ದಿಷ್ಟ ಸಂಖ್ಯೆಯೊಂದಿಗೆ ವಿನಿಮಯ ಮಾಡಿಕೊಳ್ಳುವ ಮೂಲಕ ಪಟ್ಟಿಯ ಅಂತ್ಯಕ್ಕೆ ಸರಿಸುವುದು. ಇದು ನಿಷ್ಕಪಟ ಅನುಷ್ಠಾನಕ್ಕೆ ಹೋಲಿಸಿದರೆ ಅಲ್ಗಾರಿದಮ್ನ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಕಡಿಮೆ ಮಾಡುತ್ತದೆ. ಈ ಬದಲಾವಣೆಯು ಈ ಕೆಳಗಿನ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ನೀಡುತ್ತದೆ (ಶೂನ್ಯ-ಆಧಾರಿತ ರಚನೆಗೆ). --n ಅಂಶಗಳ ಒಂದು ಶ್ರೇಣಿಯನ್ನು (ಸೂಚ್ಯಂಕಗಳು 0.n-1) ಷಫಲ್ ಮಾಡಲುಃ i ಗೆ n − 1 ರಿಂದ 1 ರವರೆಗೆ ಯಾದೃಚ್ಛಿಕ ಪೂರ್ಣಾಂಕವನ್ನು ಮಾಡಿ, ಅಂದರೆ 0 ≤ j ≤ i a [j] ಮತ್ತು a [i] ಅನ್ನು ವಿನಿಮಯ ಮಾಡಿಕೊಳ್ಳಿ, ಇದು ರಚನೆಯನ್ನು ವಿರುದ್ಧ ದಿಕ್ಕಿನಲ್ಲಿ (ಕಡಿಮೆ ಸೂಚ್ಯಂಕದಿಂದ ಮೇಲಕ್ಕೆ) ಷಫಲ್ ಮಾಡುವ ಸಮಾನ ಆವೃತ್ತಿಯಾಗಿದೆಃ-- n ಅಂಶಗಳ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಷಫಲ್ ಮಾಡಲು (ಸೂಚ್ಯಂಕಗಳು 0.n-1): i ಗೆ 0 ರಿಂದ n − 2 ಗೆ ಯಾದೃಚ್ಛಿಕ ಪೂರ್ಣಾಂಕವನ್ನು ಮಾಡಿ, ಅಂದರೆ i ≤ j <n a [i] ಮತ್ತು a [j] ಅನ್ನು ವಿನಿಮಯ ಮಾಡಿಕೊಳ್ಳಿ ಉದಾಹರಣೆಗಳು ಪೆನ್ಸಿಲ್-ಮತ್ತು-ಪೇಪರ್ ವಿಧಾನ ಈ ಉದಾಹರಣೆಯು ಫಿಶರ್ ಮತ್ತು ಯೇಟ್ಸ್ನ ಮೂಲ ವಿಧಾನವನ್ನು ಬಳಸಿಕೊಂಡು A ನಿಂದ H ಗೆ ಅಕ್ಷರಗಳನ್ನು ಕ್ರಮಗೊಳಿಸುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, ಜೆ = 3 ಆಗಿದ್ದರೆ, ಸ್ಕ್ರಾಚ್ ಪ್ಯಾಡ್ನಲ್ಲಿ ಮೂರನೇ ಅಕ್ಷರವನ್ನು ಹೊಡೆದು ಅದನ್ನು ಪರಿಣಾಮವಾಗಿ ಬರೆಯಲಾಗುತ್ತದೆಃ ಎರಡನೇ ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆಯನ್ನು ಆಯ್ಕೆ ಮಾಡಲಾಗುತ್ತದೆ, ಈ ಬಾರಿ 1 ರಿಂದ 7 ರವರೆಗೆ. ಸಂಖ್ಯೆಯು 4 ಆಗಿದ್ದರೆ, ಸ್ಕ್ರಾಚ್ ಪ್ಯಾಡ್ನಿಂದ ಇನ್ನೂ ಹೊಡೆದ ನಾಲ್ಕನೇ ಅಕ್ಷರವನ್ನು ಹೊಡೆದು ಅದನ್ನು ಫಲಿತಾಂಶಕ್ಕೆ ಸೇರಿಸಲಾಗುತ್ತದೆಃ ಮುಂದಿನ ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆಯನ್ನು 1 ರಿಂದ 6 ರವರೆಗೆ ಆಯ್ಕೆ ಮಾಡಲಾಗುತ್ತದೆ, ಮತ್ತು ನಂತರ 1 ರಿಂದ 5 ರವರೆಗೆ, ಮತ್ತು ಹೀಗೆ, ಯಾವಾಗಲೂ ಮೇಲಿನಂತೆ ಸ್ಟ್ರೈಕ್-ಔಟ್ ಪ್ರಕ್ರಿಯೆಯನ್ನು ಪುನರಾವರ್ತಿಸುತ್ತದೆಃ ಡರ್ಸ್ಟನ್ಫೆಲ್ಡ್ನ ಅಲ್ಗಾರಿದಮ್ನ ಆಧುನಿಕ ವಿಧಾನವು, ಆಯ್ಕೆ ಮಾಡಿದ ಅಕ್ಷರಗಳನ್ನು ಹೊಡೆದು ಬೇರೆಡೆ ನಕಲಿಸುವ ಬದಲು, ಅವುಗಳನ್ನು ಇನ್ನೂ ಆಯ್ಕೆ ಮಾಡದ ಕೊನೆಯ ಅಕ್ಷರದೊಂದಿಗೆ ಬದಲಾಯಿಸಲಾಗುತ್ತದೆ. ಮೊದಲಿನಂತೆಯೇ ಎ ನಿಂದ ಎಚ್ ವರೆಗಿನ ಅಕ್ಷರಗಳಿಂದ ಪ್ರಾರಂಭಿಸಿಃ 1 ರಿಂದ 8 ರವರೆಗಿನ ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆ ಜೆ ಅನ್ನು ಆಯ್ಕೆ ಮಾಡಿ, ನಂತರ ಜೆ ಮತ್ತು 8 ನೇ ಅಕ್ಷರಗಳನ್ನು ವಿನಿಮಯ ಮಾಡಿಕೊಳ್ಳಿ. ಆದ್ದರಿಂದ, ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆಯು 6 ಆಗಿದ್ದರೆ, ಉದಾಹರಣೆಗೆ, ಪಟ್ಟಿಯಲ್ಲಿರುವ 6ನೇ ಮತ್ತು 8ನೇ ಅಕ್ಷರಗಳನ್ನು ಬದಲಾಯಿಸಿಃ ಮುಂದಿನ ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆಯನ್ನು 1ರಿಂದ 7ಕ್ಕೆ ಆಯ್ಕೆ ಮಾಡಲಾಗುತ್ತದೆ ಮತ್ತು ಆಯ್ದ ಅಕ್ಷರವನ್ನು 7ನೇ ಅಕ್ಷರದೊಂದಿಗೆ ಬದಲಾಯಿಸಲಾಗುತ್ತದೆ. ಇದು 2 ಆಗಿದ್ದರೆ, ಉದಾಹರಣೆಗೆ, 2 ನೇ ಮತ್ತು 7 ನೇ ಅಕ್ಷರಗಳನ್ನು ಬದಲಾಯಿಸಿಃ ಕ್ರಮಪಲ್ಲಟನೆ ಪೂರ್ಣಗೊಳ್ಳುವವರೆಗೆ ಪ್ರಕ್ರಿಯೆಯನ್ನು ಪುನರಾವರ್ತಿಸಲಾಗುತ್ತದೆಃ ಎಂಟು ಹಂತಗಳ ನಂತರ, ಕ್ರಮಾವಳಿ ಪೂರ್ಣಗೊಳ್ಳುತ್ತದೆ ಮತ್ತು ಪರಿಣಾಮವಾಗಿ ಕ್ರಮಪಲ್ಲಟನೆಯು ಜಿ. ಇ. ಡಿ. ಸಿ. ಎ. ಎಚ್. ಬಿ. ಎಫ್. ಆಗಿದೆ. ರೂಪಾಂತರಗಳು "ಇನ್ಸೈಡ್-ಔಟ್" ಕ್ರಮಾವಳಿ ಡರ್ಸ್ಟನ್ಫೆಲ್ಡ್ ಕಾರ್ಯಗತಗೊಳಿಸಿದಂತೆ ಫಿಶರ್-ಯೇಟ್ಸ್ ಷಫಲ್, ಇನ್-ಪ್ಲೇಸ್ ಷಫಲ್ ಆಗಿದೆ. ಅಂದರೆ, ಪೂರ್ವಭಾವಿ ರಚನೆಯನ್ನು ನೀಡಿದರೆ, ಇದು ರಚನೆಯ ಬದಲಾದ ನಕಲನ್ನು ಉತ್ಪಾದಿಸುವ ಬದಲು ರಚನೆಯ ಅಂಶಗಳನ್ನು ಬದಲಿಸುತ್ತದೆ. ಷಫಲ್ ಮಾಡಬೇಕಾದ ರಚನೆಯು ದೊಡ್ಡದಾಗಿದ್ದರೆ ಇದು ಒಂದು ಪ್ರಯೋಜನವಾಗಬಹುದು. ಏಕಕಾಲದಲ್ಲಿ ರಚನೆಯನ್ನು ಪ್ರಾರಂಭಿಸಲು ಮತ್ತು ಷಫಲ್ ಮಾಡಲು, ಷಫಲ್ನ "ಇನ್ಸೈಡ್-ಔಟ್" ಆವೃತ್ತಿಯನ್ನು ಮಾಡುವ ಮೂಲಕ ಸ್ವಲ್ಪ ಹೆಚ್ಚು ದಕ್ಷತೆಯನ್ನು ಸಾಧಿಸಬಹುದು. ಈ ಆವೃತ್ತಿಯಲ್ಲಿ, ಈ ಹಿಂದೆ ಆ ಸ್ಥಾನವನ್ನು ಆಕ್ರಮಿಸಿಕೊಂಡಿದ್ದ ಅಂಶವನ್ನು i ಸ್ಥಾನಕ್ಕೆ ಸ್ಥಳಾಂತರಿಸಿದ ನಂತರ, ಅನುಕ್ರಮವಾಗಿ ಅಂಶ ಸಂಖ್ಯೆ i ಅನ್ನು ರಚನೆಯಲ್ಲಿನ ಮೊದಲ i ಸ್ಥಾನಗಳ ನಡುವೆ ಯಾದೃಚ್ಛಿಕ ಸ್ಥಾನಕ್ಕೆ ಇರಿಸಲಾಗುತ್ತದೆ. ಯಾದೃಚ್ಛಿಕ ಸ್ಥಾನವು ಸಂಖ್ಯೆ i ಆಗಿದ್ದರೆ, ಈ "ಚಲನೆ" (ಅದೇ ಸ್ಥಳಕ್ಕೆ) ಪ್ರಾರಂಭಿಸದ ಮೌಲ್ಯವನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ, ಆದರೆ ಅದು ಅಪ್ರಸ್ತುತವಾಗುತ್ತದೆ, ಏಕೆಂದರೆ ಮೌಲ್ಯವನ್ನು ತಕ್ಷಣವೇ ತಿದ್ದಿ ಬರೆಯಲಾಗುತ್ತದೆ. ಯಾವುದೇ ಪ್ರತ್ಯೇಕ ಆರಂಭದ ಅಗತ್ಯವಿಲ್ಲ, ಮತ್ತು ಯಾವುದೇ ವಿನಿಮಯವನ್ನು ನಡೆಸಲಾಗುವುದಿಲ್ಲ. 0 ರಿಂದ n−1 ರವರೆಗಿನ ಪೂರ್ಣಾಂಕಗಳಂತಹ ಕೆಲವು ಸರಳ ಕಾರ್ಯಗಳಿಂದ ಮೂಲವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿರುವ ಸಾಮಾನ್ಯ ಸಂದರ್ಭದಲ್ಲಿ, ಕಾರ್ಯಗತಗೊಳಿಸುವ ಸಮಯದಲ್ಲಿ ಮೂಲವನ್ನು ಎಂದಿಗೂ ಬದಲಾಯಿಸದ ಕಾರಣ ಮೂಲವನ್ನು ಸರಳವಾಗಿ ಕಾರ್ಯದಿಂದ ಬದಲಾಯಿಸಬಹುದು. n ಅಂಶಗಳ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಯಾದೃಚ್ಛಿಕವಾಗಿ ಬದಲಾದ ಮೂಲದ ನಕಲಿಗೆ ಪ್ರಾರಂಭಿಸಲು, ಎರಡೂ 0-ಆಧಾರಿತಃ 0 ರಿಂದ n − 1 ರವರೆಗಿನ i ಗೆ, 0 ≤ j ≤ i ಆಗಿದ್ದರೆ, n ಅಂಶಗಳ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಪ್ರಾರಂಭಿಸಲು, 0 ≤ j ≤ i ಆಗಿದ್ದರೆ, j ≤ 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 ರಲ್ಲಿ, ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆ ಜೆ ಅನ್ನು ನಡುವಿನ ವ್ಯಾಪ್ತಿಯಿಂದ ಆಯ್ಕೆ ಮಾಡಲಾಗಿದೆ. ಈ ಸರಳ ಬದಲಾವಣೆಯು ಕ್ರಮಾವಳಿಯನ್ನು ಮಾರ್ಪಡಿಸುತ್ತದೆ, ಇದರಿಂದಾಗಿ ಫಲಿತಾಂಶದ ಕ್ರಮಪಲ್ಲಟನೆಯು ಯಾವಾಗಲೂ ಒಂದೇ ಚಕ್ರವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ವಾಸ್ತವವಾಗಿ, ಕೆಳಗೆ ವಿವರಿಸಿದಂತೆ, ಸಾಮಾನ್ಯ ಫಿಶರ್-ಯೇಟ್ಸ್ ಷಫಲ್ ಅನ್ನು ಉದ್ದೇಶಿಸಿದಾಗ ಆಕಸ್ಮಿಕವಾಗಿ ಸಟೊಲೊನ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸುವುದು ತುಂಬಾ ಸುಲಭ. ಇದು (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 ವಸ್ತುಗಳು [ಜೆ], ವಸ್ತುಗಳು [ಐ] = ವಸ್ತುಗಳು [ಐ], ವಸ್ತುಗಳು [ಜೆ] ಇತರ ಷಫ್ಲಿಂಗ್ ಕ್ರಮಾವಳಿಗಳೊಂದಿಗೆ ಹೋಲಿಕೆ ಫಿಶರ್-ಯೇಟ್ಸ್ ಷಫಲ್ನ ಲಕ್ಷಣರಹಿತ ಸಮಯ ಮತ್ತು ಸ್ಥಳ ಸಂಕೀರ್ಣತೆಯು ಸೂಕ್ತವಾಗಿದೆ. ಉತ್ತಮ-ಗುಣಮಟ್ಟದ ಪಕ್ಷಪಾತವಿಲ್ಲದ ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆಯ ಮೂಲದೊಂದಿಗೆ, ಇದು ಪಕ್ಷಪಾತವಿಲ್ಲದ ಫಲಿತಾಂಶಗಳನ್ನು ನೀಡುತ್ತದೆ ಎಂದು ಖಾತರಿಪಡಿಸಲಾಗಿದೆ. ಇತರ ಕೆಲವು ಪರಿಹಾರಗಳಿಗೆ ಹೋಲಿಸಿದರೆ, ಫಲಿತಾಂಶದ ಕ್ರಮಪಲ್ಲಟನೆಯ ಒಂದು ಭಾಗ ಮಾತ್ರ ಅಗತ್ಯವಿದ್ದರೆ, ಅದನ್ನು ಅರ್ಧದಾರಿಯಲ್ಲೇ ನಿಲ್ಲಿಸಬಹುದು, ಅಥವಾ ನಿಲ್ಲಿಸಬಹುದು ಮತ್ತು ಪದೇ ಪದೇ ಪುನರಾರಂಭಿಸಬಹುದು, ಅಗತ್ಯವಿರುವಂತೆ ಕ್ರಮಪಲ್ಲಟನೆಯನ್ನು ಹೆಚ್ಚಿಸಬಹುದು. ನಿಷ್ಕಪಟ ವಿಧಾನವು ಎಲ್ಲಾ ಅಂಶಗಳಿಂದ ಯಾದೃಚ್ಛಿಕವಾಗಿ ಆಯ್ಕೆ ಮಾಡಲಾದ ಮತ್ತೊಂದು ಅಂಶದೊಂದಿಗೆ ಪ್ರತಿ ಅಂಶವನ್ನು ವಿನಿಮಯ ಮಾಡಿಕೊಳ್ಳುವ ನಿಷ್ಕಪಟ ವಿಧಾನವು ಪಕ್ಷಪಾತದಿಂದ ಕೂಡಿದೆ. ವಿಭಿನ್ನ ಕ್ರಮಪಲ್ಲಟನೆಗಳು ಪ್ರತಿಯೊಂದಕ್ಕೂ ಉತ್ಪತ್ತಿಯಾಗುವ ವಿಭಿನ್ನ ಸಂಭವನೀಯತೆಗಳನ್ನು ಹೊಂದಿರುತ್ತವೆ, ಏಕೆಂದರೆ ವಿಭಿನ್ನ ಕ್ರಮಪಲ್ಲಟನೆಗಳ ಸಂಖ್ಯೆಯು ಕ್ರಮಾವಳಿಯ ಯಾದೃಚ್ಛಿಕ ಫಲಿತಾಂಶಗಳ ಸಂಖ್ಯೆಯನ್ನು ಸಮಾನವಾಗಿ ವಿಭಜಿಸುವುದಿಲ್ಲ. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ಬರ್ಟ್ರಾಂಡ್ನ ಪ್ರತಿಪಾದನೆಯ ಪ್ರಕಾರ, ಮತ್ತು ನಡುವೆ ಕನಿಷ್ಠ ಒಂದು ಅವಿಭಾಜ್ಯ ಸಂಖ್ಯೆ ಇರುತ್ತದೆ, ಮತ್ತು ಈ ಸಂಖ್ಯೆಯು ಭಾಗಿಸುತ್ತದೆ ಆದರೆ ಭಾಗಿಸುವುದಿಲ್ಲ. ಯಾದೃಚ್ಛಿಕ ಆಮದಿನಿಂದ ರಾಂಡ್ರೇಂಜ್ ಡೆಫ್ ನೈವ್ _ ಷಫಲ್ (ಐಟಂಗಳು)-> ಯಾವುದೂ ಇಲ್ಲಃ "" ಒಂದು ನಿಷ್ಕಪಟ ವಿಧಾನ. ಏನು ಮಾಡಬಾರದು ಎಂಬುದಕ್ಕೆ ಇದು ಒಂದು ಉದಾಹರಣೆಯಾಗಿದೆ-ಬದಲಿಗೆ ಫಿಶರ್-ಯೇಟ್ಸ್ ಅನ್ನು ಬಳಸಿ. ಎನ್ = ಲೆನ್ (ಐಟಂಗಳು) ಫಾರ್ ಐ ಇನ್ ರೇಂಜ್ (ಎನ್): ಜೆ = ರಾಂಡ್ರೇಂಜ್ (ಎನ್) #0 <= ಜೆ <= ಎನ್-1 ಐಟಂಗಳು [ಜೆ], ಐಟಂಗಳು [ಐ] = ಐಟಂಗಳು [ಐ], ಐಟಂಗಳು [ಜೆ] ವಿಂಗಡಣೆ ಒಂದು ಪರ್ಯಾಯ ವಿಧಾನವು ಗುಂಪಿನ ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆಯನ್ನು ನಿಯೋಜಿಸುತ್ತದೆ ಮತ್ತು ನಂತರ ನಿಗದಿಪಡಿಸಿದ ಸಂಖ್ಯೆಗಳಿಗೆ ಅನುಗುಣವಾಗಿ ಸೆಟ್ ಅನ್ನು ವಿಂಗಡಿಸುತ್ತದೆ. ವಿಂಗಡಣಾ ವಿಧಾನವು ಫಿಶರ್-ಯೇಟ್ಸ್ನಂತೆಯೇ ಅದೇ ಲಕ್ಷಣರಹಿತ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿದೆಃ ಸಾಮಾನ್ಯ ವಿಂಗಡಣೆ ಒ (ಎನ್ ಲಾಗ್ ಎನ್) ಆಗಿದ್ದರೂ, ಓ (ಎನ್) ಸಮಯದಲ್ಲಿ ರಾಡಿಕ್ಸ್ ವಿಂಗಡಣೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಸಂಖ್ಯೆಗಳನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ವಿಂಗಡಿಸಲಾಗುತ್ತದೆ. ಫಿಶರ್-ಯೇಟ್ಸ್ ಷಫಲ್ನಂತೆ, ವಿಂಗಡಣಾ ವಿಧಾನವು ಪಕ್ಷಪಾತವಿಲ್ಲದ ಫಲಿತಾಂಶಗಳನ್ನು ನೀಡುತ್ತದೆ. ಆದಾಗ್ಯೂ, ನಿಗದಿಪಡಿಸಿದ ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆಗಳನ್ನು ಎಂದಿಗೂ ನಕಲು ಮಾಡಲಾಗುವುದಿಲ್ಲ ಎಂದು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಲು ಕಾಳಜಿಯನ್ನು ತೆಗೆದುಕೊಳ್ಳಬೇಕು, ಏಕೆಂದರೆ ವಿಂಗಡಣಾ ಕ್ರಮಾವಳಿಗಳು ಸಾಮಾನ್ಯವಾಗಿ ಟೈ ಸಂದರ್ಭದಲ್ಲಿ ಯಾದೃಚ್ಛಿಕವಾಗಿ ಅಂಶಗಳನ್ನು ಆದೇಶಿಸುವುದಿಲ್ಲ. ಹೆಚ್ಚುವರಿಯಾಗಿ, ಈ ವಿಧಾನಕ್ಕೆ ಲಕ್ಷಣರಹಿತವಾಗಿ ದೊಡ್ಡ ಸ್ಥಳಾವಕಾಶದ ಅಗತ್ಯವಿರುತ್ತದೆಃ ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆಗಳಿಗೆ O (n) ಹೆಚ್ಚುವರಿ ಶೇಖರಣಾ ಸ್ಥಳ, ಮತ್ತು ಫಿಶರ್-ಯೇಟ್ಸ್ ಷಫಲ್ಗೆ O (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 ಅನ್ನು ಭಾಗಿಸುವುದಿಲ್ಲಃ 100ಕ್ಕಿಂತ ಕಡಿಮೆ ಅಥವಾ ಸಮನಾದ 16ರ ಅತಿದೊಡ್ಡ ಗುಣಾಕಾರವು 6 × 16 = 96 ಆಗಿದೆ, ಮತ್ತು ಅಪೂರ್ಣ ಶ್ರೇಣಿಯ 96-99 ನಲ್ಲಿರುವ ಸಂಖ್ಯೆಗಳೇ ಪಕ್ಷಪಾತಕ್ಕೆ ಕಾರಣವಾಗುತ್ತವೆ. ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಸರಳವಾದ ಮಾರ್ಗವೆಂದರೆ ಉಳಿದವನ್ನು ತೆಗೆದುಕೊಳ್ಳುವ ಮೊದಲು ಆ ಸಂಖ್ಯೆಗಳನ್ನು ತ್ಯಜಿಸುವುದು ಮತ್ತು ಸೂಕ್ತ ಶ್ರೇಣಿಯಲ್ಲಿರುವ ಸಂಖ್ಯೆಯು ಬರುವವರೆಗೆ ಮತ್ತೆ ಪ್ರಯತ್ನಿಸುವುದು. ತಾತ್ವಿಕವಾಗಿ ಇದು, ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ, ಶಾಶ್ವತವಾಗಿ ತೆಗೆದುಕೊಳ್ಳಬಹುದಾದರೂ, ನಿರೀಕ್ಷಿತ ಸಂಖ್ಯೆಯ ಮರುಪ್ರಯತ್ನಗಳು ಯಾವಾಗಲೂ ಒಂದಕ್ಕಿಂತ ಕಡಿಮೆಯಿರುತ್ತವೆ. ಅನುಷ್ಠಾನಗಳೊಂದಿಗೆ ಸಂಬಂಧಿತ ಸಮಸ್ಯೆಯು ಸಂಭವಿಸುತ್ತದೆ, ಅದು ಮೊದಲು ಯಾದೃಚ್ಛಿಕ ಫ್ಲೋಟಿಂಗ್-ಪಾಯಿಂಟ್ ಸಂಖ್ಯೆಯನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ-ಸಾಮಾನ್ಯವಾಗಿ ವ್ಯಾಪ್ತಿಯಲ್ಲಿ [0,1]-ಮತ್ತು ನಂತರ ಅದನ್ನು ಬಯಸಿದ ವ್ಯಾಪ್ತಿಯ ಗಾತ್ರದಿಂದ ಗುಣಿಸಿ ಮತ್ತು ಕೆಳಗೆ ಸುತ್ತುತ್ತದೆ. ಇಲ್ಲಿ ಸಮಸ್ಯೆಯೆಂದರೆ, ಯಾದೃಚ್ಛಿಕ ಫ್ಲೋಟಿಂಗ್-ಪಾಯಿಂಟ್ ಸಂಖ್ಯೆಗಳು, ಎಷ್ಟೇ ಎಚ್ಚರಿಕೆಯಿಂದ ಉತ್ಪತ್ತಿಯಾಗಿದ್ದರೂ, ಯಾವಾಗಲೂ ಸೀಮಿತ ನಿಖರತೆಯನ್ನು ಮಾತ್ರ ಹೊಂದಿರುತ್ತವೆ. ಇದರರ್ಥ ಯಾವುದೇ ನಿರ್ದಿಷ್ಟ ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ಸೀಮಿತ ಸಂಖ್ಯೆಯ ಫ್ಲೋಟಿಂಗ್ ಪಾಯಿಂಟ್ ಮೌಲ್ಯಗಳು ಮಾತ್ರ ಇವೆ, ಮತ್ತು ಶ್ರೇಣಿಯನ್ನು ಈ ಸಂಖ್ಯೆಯನ್ನು ಸಮವಾಗಿ ವಿಭಜಿಸದ ಹಲವಾರು ವಿಭಾಗಗಳಾಗಿ ವಿಂಗಡಿಸಿದರೆ, ಕೆಲವು ವಿಭಾಗಗಳು ಇತರರಿಗಿಂತ ಹೆಚ್ಚಿನ ಸಂಭವನೀಯ ಮೌಲ್ಯಗಳೊಂದಿಗೆ ಕೊನೆಗೊಳ್ಳುತ್ತವೆ. ಪರಿಣಾಮವಾಗಿ ಬರುವ ಪಕ್ಷಪಾತವು ಹಿಂದಿನ ಪ್ರಕರಣದಂತೆಯೇ ಅದೇ ವ್ಯವಸ್ಥಿತ ಕೆಳಮುಖ ಪ್ರವೃತ್ತಿಯನ್ನು ತೋರಿಸುವುದಿಲ್ಲವಾದರೂ, ಅದು ಇನ್ನೂ ಇರುತ್ತದೆ. ಸ್ಯೂಡೋರಾಂಡಮ್ ಜನರೇಟರ್ಗಳು ಫಿಶರ್-ಯೇಟ್ಸ್ ಷಫಲ್ ಅನ್ನು ಸ್ಯೂಡೋರಾಂಡಮ್ ಸಂಖ್ಯೆ ಜನರೇಟರ್ ಅಥವಾ ಪಿಆರ್ಎನ್ಜಿಯೊಂದಿಗೆ ಬಳಸಿದಾಗ ಹೆಚ್ಚುವರಿ ಸಮಸ್ಯೆ ಉಂಟಾಗುತ್ತದೆಃ ಅಂತಹ ಜನರೇಟರ್ನಿಂದ ಸಂಖ್ಯೆಗಳ ಉತ್ಪಾದನೆಯ ಅನುಕ್ರಮವನ್ನು ಅನುಕ್ರಮದ ಆರಂಭದಲ್ಲಿ ಅದರ ಆಂತರಿಕ ಸ್ಥಿತಿಯಿಂದ ಸಂಪೂರ್ಣವಾಗಿ ನಿರ್ಧರಿಸಲಾಗುತ್ತದೆ, ಅಂತಹ ಜನರೇಟರ್ನಿಂದ ನಡೆಸಲ್ಪಡುವ ಷಫಲ್ ಜನರೇಟರ್ ವಿಶಿಷ್ಟವಾದ ಸಂಭವನೀಯ ಸ್ಥಿತಿಗಳನ್ನು ಹೊಂದಿರುವುದಕ್ಕಿಂತ ಹೆಚ್ಚು ವಿಭಿನ್ನವಾದ ಕ್ರಮಪಲ್ಲಟನೆಗಳನ್ನು ಉತ್ಪಾದಿಸಲು ಸಾಧ್ಯವಿಲ್ಲ. ಸಂಭವನೀಯ ಸ್ಥಿತಿಗಳ ಸಂಖ್ಯೆಯು ಕ್ರಮಪಲ್ಲಟನೆಗಳ ಸಂಖ್ಯೆಯನ್ನು ಮೀರಿದಾಗಲೂ, ಸಂಖ್ಯೆಗಳ ಅನುಕ್ರಮಗಳಿಂದ ಕ್ರಮಪಲ್ಲಟನೆಗಳವರೆಗಿನ ನಕ್ಷೆಯ ಅನಿಯಮಿತ ಸ್ವರೂಪವು ಕೆಲವು ಕ್ರಮಪಲ್ಲಟನೆಗಳು ಇತರರಿಗಿಂತ ಹೆಚ್ಚಾಗಿ ಸಂಭವಿಸುತ್ತವೆ ಎಂದರ್ಥ. ಹೀಗಾಗಿ, ಪಕ್ಷಪಾತವನ್ನು ಕಡಿಮೆ ಮಾಡಲು, ಪಿ. ಆರ್. ಎನ್. ಜಿ. ಯ ಸ್ಥಿತಿಗಳ ಸಂಖ್ಯೆಯು ಕ್ರಮಪಲ್ಲಟನೆಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕನಿಷ್ಠ ಪ್ರಮಾಣದ ಹಲವಾರು ಕ್ರಮಗಳಿಂದ ಮೀರಬೇಕು. ಉದಾಹರಣೆಗೆ, ಅನೇಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಭಾಷೆಗಳು ಮತ್ತು/ಅಥವಾ ಗ್ರಂಥಾಲಯಗಳು ಒದಗಿಸಿದ ಅಂತರ್ನಿರ್ಮಿತ ಸೂಡೊರಾಂಡಮ್ ಸಂಖ್ಯೆ ಜನರೇಟರ್ ಸಾಮಾನ್ಯವಾಗಿ ಕೇವಲ 32 ಬಿಟ್ಗಳ ಆಂತರಿಕ ಸ್ಥಿತಿಯನ್ನು ಹೊಂದಿರಬಹುದು, ಅಂದರೆ ಇದು ಕೇವಲ 232 ವಿಭಿನ್ನ ಅನುಕ್ರಮ ಸಂಖ್ಯೆಗಳನ್ನು ಮಾತ್ರ ಉತ್ಪಾದಿಸುತ್ತದೆ. ಅಂತಹ ಜನರೇಟರ್ ಅನ್ನು 52 ಪ್ಲೇಯಿಂಗ್ ಕಾರ್ಡ್ಗಳ ಡೆಕ್ ಅನ್ನು ಷಫಲ್ ಮಾಡಲು ಬಳಸಿದರೆ, ಅದು 52 ರ ಒಂದು ಸಣ್ಣ ಭಾಗವನ್ನು ಮಾತ್ರ ಉತ್ಪಾದಿಸುತ್ತದೆ! ≈ 2225.6 ಸಂಭವನೀಯ ಕ್ರಮಪಲ್ಲಟನೆಗಳು. 226 ಬಿಟ್ಗಳಿಗಿಂತ ಕಡಿಮೆ ಆಂತರಿಕ ಸ್ಥಿತಿಯನ್ನು ಹೊಂದಿರುವ ಜನರೇಟರ್ಗೆ 52-ಕಾರ್ಡ್ ಡೆಕ್ನ ಎಲ್ಲಾ ಸಂಭವನೀಯ ಕ್ರಮಪಲ್ಲಟನೆಗಳನ್ನು ಉತ್ಪಾದಿಸುವುದು ಅಸಾಧ್ಯ. ಯಾವುದೇ ಸೂಡೊರಾಂಡಮ್ ಸಂಖ್ಯೆ ಜನರೇಟರ್ ಅನ್ನು ಪ್ರಾರಂಭಿಸುವ ಹಂತದಿಂದ ಪ್ರಾರಂಭಿಸಿ, ಅದನ್ನು ಪ್ರಾರಂಭಿಸಬಹುದಾದ ವಿಭಿನ್ನ ಬೀಜ ಮೌಲ್ಯಗಳಿಗಿಂತ ಹೆಚ್ಚು ವಿಭಿನ್ನ ಅನುಕ್ರಮಗಳನ್ನು ಉತ್ಪಾದಿಸಲು ಸಾಧ್ಯವಿಲ್ಲ. ಹೀಗಾಗಿ, 1024 ಬಿಟ್ಗಳ ಆಂತರಿಕ ಸ್ಥಿತಿಯನ್ನು ಹೊಂದಿರುವ ಆದರೆ 32-ಬಿಟ್ ಬೀಜದಿಂದ ಪ್ರಾರಂಭಿಸಲಾದ ಜನರೇಟರ್, ಆರಂಭದ ನಂತರವೂ 232 ವಿಭಿನ್ನ ಕ್ರಮಪಲ್ಲಟನೆಗಳನ್ನು ಮಾತ್ರ ಉತ್ಪಾದಿಸಬಹುದು. ಕ್ರಮಪಲ್ಲಟನೆಗಳನ್ನು ಉತ್ಪಾದಿಸಲು ಜನರೇಟರ್ ಅನ್ನು ಬಳಸಲು ಪ್ರಾರಂಭಿಸುವ ಮೊದಲು ಅದನ್ನು ಅನೇಕ ಬಾರಿ ಬಳಸಿದರೆ ಅದು ಹೆಚ್ಚಿನ ಕ್ರಮಪಲ್ಲಟನೆಗಳನ್ನು ಉಂಟುಮಾಡಬಹುದು, ಆದರೆ ಇದು ಯಾದೃಚ್ಛಿಕತೆಯನ್ನು ಹೆಚ್ಚಿಸುವ ಅತ್ಯಂತ ಅದಕ್ಷ ಮಾರ್ಗವಾಗಿದೆಃ ಜನರೇಟರ್ ಅನ್ನು ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆಯನ್ನು ಒಂದು ಬಿಲಿಯನ್ ವರೆಗೆ ಬಳಸಲು ವ್ಯವಸ್ಥೆ ಮಾಡಬಹುದು ಎಂದು ಭಾವಿಸೋಣ, ಸರಳತೆಗಾಗಿ 230 ಎಂದು ಹೇಳಿ, ಪ್ರಾರಂಭ ಮತ್ತು ಕ್ರಮಪಲ್ಲಟನೆಗಳನ್ನು ಉತ್ಪಾದಿಸುವ ನಡುವಿನ ಸಮಯಗಳು, ನಂತರ ಸಂಭವನೀಯ ಕ್ರಮಪಲ್ಲಟನೆಗಳ ಸಂಖ್ಯೆ ಇನ್ನೂ ಕೇವಲ 262 ಆಗಿದೆ. ಮೇಲೆ ವಿವರಿಸಿದ ವ್ಯಾಪ್ತಿ ಕಡಿತದ ವಿಭಜನೆ-ಮತ್ತು-ತೆಗೆದುಕೊಳ್ಳುವಿಕೆ-ಉಳಿಸಿಕೊಳ್ಳುವ ವಿಧಾನದೊಂದಿಗೆ ಸರಳ ರೇಖೀಯ ಏಕರೂಪದ ಪಿ. ಆರ್. ಎನ್. ಜಿ. ಯನ್ನು ಬಳಸಿದಾಗ ಮತ್ತೊಂದು ಸಮಸ್ಯೆ ಉಂಟಾಗುತ್ತದೆ. ಇಲ್ಲಿ ಸಮಸ್ಯೆಯೆಂದರೆ, ಮಾಡ್ಯುಲೋ 2e ಯೊಂದಿಗೆ ರೇಖೀಯ ಏಕರೂಪದ PRNG ಯ ಕಡಿಮೆ-ಕ್ರಮಾಂಕದ ಬಿಟ್ಗಳು ಉನ್ನತ-ಕ್ರಮಾಂಕದ ಬಿಟ್ಗಳಿಗಿಂತ ಕಡಿಮೆ ಯಾದೃಚ್ಛಿಕವಾಗಿರುತ್ತವೆಃ ಜನರೇಟರ್ನ ಕಡಿಮೆ n ಬಿಟ್ಗಳು ಗರಿಷ್ಠ 2n ಅವಧಿಯನ್ನು ಹೊಂದಿರುತ್ತವೆ. ವಿಭಾಜಕವು ಎರಡರ ಶಕ್ತಿಯಾಗಿದ್ದಾಗ, ಉಳಿದದ್ದನ್ನು ತೆಗೆದುಕೊಳ್ಳುವುದು ಎಂದರೆ ಉನ್ನತ-ಕ್ರಮಾಂಕದ ಬಿಟ್ಗಳನ್ನು ಎಸೆಯುವುದು ಎಂದರ್ಥ, ಅಂದರೆ ಒಂದು ಗಮನಾರ್ಹವಾಗಿ ಕಡಿಮೆ ಯಾದೃಚ್ಛಿಕ ಮೌಲ್ಯದೊಂದಿಗೆ ಕೊನೆಗೊಳ್ಳುತ್ತದೆ. ಎಲ್ಸಿಜಿ ಪ್ರೈಮ್ ಮಾಡ್ಯುಲೋವನ್ನು ಹೊಂದಿದ್ದರೆ ವಿಭಿನ್ನ ನಿಯಮಗಳು ಅನ್ವಯಿಸುತ್ತವೆ, ಆದರೆ ಅಂತಹ ಜನರೇಟರ್ಗಳು ಅಪರೂಪ. ಕಳಪೆ-ಗುಣಮಟ್ಟದ ಆರ್ಎನ್ಜಿ ಅಥವಾ ಪಿಆರ್ಎನ್ಜಿ ಕಳಪೆ-ಗುಣಮಟ್ಟದ ಷಫಲ್ಗಳನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ ಎಂಬ ಸಾಮಾನ್ಯ ನಿಯಮಕ್ಕೆ ಇದು ಒಂದು ಉದಾಹರಣೆಯಾಗಿದೆ. ಆರ್. ಸಿ. 4 ಅನ್ನು ಸಹ ನೋಡಿ, ಒಂದು ಶ್ರೇಣಿಯ ಜಲಾಶಯದ ಮಾದರಿಯನ್ನು ಬದಲಾಯಿಸುವುದನ್ನು ಆಧರಿಸಿದ ಸ್ಟ್ರೀಮ್ ಸೈಫರ್, ನಿರ್ದಿಷ್ಟವಾಗಿ ಅಲ್ಗಾರಿದಮ್ ಆರ್ ಇದು ಫಿಶರ್-ಯೇಟ್ಸ್ ಷಫಲ್ ಉಲ್ಲೇಖಗಳ ವಿಶೇಷತೆ ಬಾಹ್ಯ ಕೊಂಡಿಗಳು ಒಂದು ಸಂವಾದಾತ್ಮಕ ಉದಾಹರಣೆ ಸಂಯೋಜಿತ ಕ್ರಮಾವಳಿಗಳು ಯಾದೃಚ್ಛಿಕ ಕ್ರಮಾವಳಿಗಳು ಕ್ರಮಪಲ್ಲಟನೆಗಳು ಮಾಂಟೆ ಕಾರ್ಲೊ ವಿಧಾನಗಳು ಉದಾಹರಣೆಗೆ ಸೂಡೊಕೋಡ್ ಲೇಖನಗಳು ಉದಾಹರಣೆಗೆ ಪೈಥಾನ್ (ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಭಾಷೆ) ಕೋಡ್ ಹೊಂದಿರುವ ಲೇಖನಗಳು