ניקח מערך ונשים בו ב-n התאים מספרים מ-1 עד n.
נבצע n פעמים (אפשר גם 5n בשביל לערבל יותר) את האיטרציה הבאה:
- נבצע הגרלה פעמיים (הגרלה מודולו n). נבצע החלפה של המספרים בין התאים i ו-j המתקבלים.
- ניתן בשביל קצת להטיב עם הערבול - אם i=j אז נבחר [j=[i/2 (למשל).

כשאני מגדיר אקראיות בפרמוטציות אני למעשה ארצה לתת לכל פרמוטציה הזדמנות שווה לצאת. יש n! תמורות. אני ארצה שאם נניח אני אבצע n!^2 עירבולים אז מבחינת התפלגות, אני אראה שכל תמורה הוגרלה מספר דומה של פעמים. לפחות ארצה לשאוף לזה.

בעייתיות הפתרון הראשוני:
נגריל מספר מ-1 עד n ואז נשים אותו בפרמוטציה. נגריל שוב מספר מ-1 עד n, ונבדוק האם טרם הוגרל. אם כן, נגריל שוב. הבדיקה הזאת יקרה, ומעבירה אותנו לסיבוכיות ריבועית.

הפתרון:
נאתחל מערך באופן ש-A[i] = i (נניח שהאינדקסים שלו הם מ-1 ועד n לצורך נוחיות).
עבור i החל מ-1 ועד n בצע:
- הגרל מספר שלם בין 1 ל-n; בצע השמה ל-j.
- החלף בין A[i] ל-A[j].

הפרמוטציה תהיה הדפסת המערך לפי סדר איבריו.

נותר להראות שלכל פרמוטציה סיכוי שווה להתקבל:
מבחינה סימטרית ניתן לראות שזה קורה.
אם יהיה זמן, אני אחשוב איך להוכיח את זה באופן ריגורוזי ופשוט יחסית ואסביר למה לכל פרמוטציה יש סיכוי של אחד חלקי n! להתקבל. אם יש לכם רעיונות מקוריים, לכו על זה.