מערבל רשימות אקראי - כלי מיקסום רשימות חינמי

מהו מערבל רשימות אקראיות?

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

כיצד להשתמש במערבל הרשימות האקראי

1. הקלידו או הדביקו את הרשימה בתיבה, פריט אחד בכל שורה.
2. לחצו על "ערבב את הרשימה". הפריטים יסתדרו מחדש מיד.
3. קראו את הרשימה המעורבבת שמתחת ללחצן, כשהפריטים ממוספרים לפי הסדר החדש.
4. לחצו שוב על "הגרל רשימה" כדי לבצע ערבול חדש ובלתי תלוי.
5. לחצו על "העתק תוצאה" כדי להעתיק את הסדר החדש, או על "נקה" כדי להתחיל מחדש.

שורות ריקות בקלט מוסרות אוטומטית, ולכן מעברי שורה נוספים לא ייצרו רשומות ריקות בתוצאות.

כיצד פועל אלגוריתם הערבול של פישר–ייטס?

ערבול פישר–ייטס עובר על הרשימה פעם אחת, החל מהפריט האחרון ובהתקדמות לכיוון ההתחלה. בכל שלב הוא בוחר באקראי פריט אחד מתוך החלק ברשימה שעדיין לא שובץ, ומחליף אותו עם הפריט שבמיקום הנוכחי.

נוסחת ערבול פישר–ייטס

עבור רשימה הכוללת n פריטים, הממוספרים ממיקום 0 עד מיקום n − 1:

1for i from n − 1 down to 1:
2    choose a random whole number j, where 0 ≤ j ≤ i
3    swap the items at positions i and j
4

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

דוגמה: ערבול רשימה של ארבעה פריטים

מתחילים בארבעה פריטים במיקומים 0 עד 3: Apple, Banana, Cherry, Date.

• i = 3: הבחירה האקראית היא j = 0. מחליפים בין המיקומים 3 ו־0 → Date, Banana, Cherry, Apple
• i = 2: הבחירה האקראית היא j = 2. החלפת מיקום עם עצמו אינה משנה דבר → Date, Banana, Cherry, Apple
• i = 1: הבחירה האקראית היא j = 0. מחליפים בין המיקומים 1 ו־0 → Banana, Date, Cherry, Apple

הסדר הסופי: Banana, Date, Cherry, Apple.

עם ארבעה פריטים יש 4! = 24 סדרים אפשריים. לכל אחד מהם, כולל הסדר הזה, יש סיכוי של 1 מתוך 24 להופיע בכל ערבול נתון.

מדוע לא פשוט להחליף זוגות אקראיים?

שיטה פשוטה יותר לכאורה — לבחור שני מיקומים אקראיים ולהחליף ביניהם, ולחזור על כך כמה פעמים — נראית אקראית, אך אינה כזו. כמה מתוכניות הערבול המוקדמות משנות ה־1950 פעלו כך, והעדיפו בשקט סדרים מסוימים על פני אחרים, אף שאף הרצה יחידה לא נראתה חשודה. ערבול פישר–ייטס מונע זאת, משום שכל פריט מוזז בדיוק פעם אחת, למיקום שנבחר מתוך קבוצת אפשרויות המצטמצמת באופן מדויק, וכך כל סדר סופי נעשה בעל סבירות שווה.

מהו מקורו של ערבול פישר–ייטס?

הסטטיסטיקאים רונלד פישר ופרנק ייטס תיארו את השיטה בשנת 1938 בספר טבלאות סטטיסטיות, לצורך ערבול ידני בעת תכנון ניסויים. בשנת 1964 ריצ'רד דורסטנפלד התאים אותה למחשבים, כך שאפשר יהיה לסדר רשימה מחדש במקומה, בלי להזדקק לרשימה שנייה שתעקוב אחר הפריטים שנותרו. דונלד קנות כלל את הגרסה הממוחשבת הזו בספרו משנת 1969, אמנות תכנות המחשבים, ולכן היא נקראת לעיתים ערבול קנות. דפדפני אינטרנט משתמשים באותו אלגוריתם גם כיום.

שימושים נפוצים במערבל רשימות

• קביעת הסדר שבו תלמידים מציגים או עונים על שאלות בכיתה
• הגרלת סדר המשחקים בטורניר או קביעת סדר התורות במשחק
• חלוקת קבוצה לצוותים אקראיים
• בחירת מסעדה, סרט או משימה מתוך רשימה מצומצמת בלי להעדיף אפשרות מסוימת

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

שאלות נפוצות

האם הערבול אקראי באמת?

הוא מסתמך על מחולל המספרים הפסאודו־אקראיים (PRNG) של דפדפן האינטרנט, נוסחה שמייצרת רצפים של מספרים המתנהגים כמו אקראיות לצרכים מעשיים. זה מספיק לסדרים בכיתה, להגרלת סדר משחקים בטורניר או לבחירת סרט. הוא אינו מיועד להצפנה, למערכות הימורים או לכל מצב שבו כסף או אבטחה תלויים בחוסר יכולת לחזות את התוצאה; למצבים כאלה דרושים מחוללי מספרים אקראיים מוסמכים.

האם הכלי שולח את הרשימה שלי לשרת?

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

מה קורה לפריטים כפולים?

פריטים כפולים נשמרים. אם "Sam" מופיע פעמיים בקלט, הוא עדיין יופיע פעמיים בפלט המעורבב, וייתכן שבמיקומים שונים.

האם יש הגבלה על מספר הפריטים שאפשר לערבל?

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

במה שונה ערבול ממיון?

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

האם אפשר לערבל את אותה רשימה יותר מפעם אחת?

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