הרצנו מתנה קטנה להשקת Toolz, ועשיתי את הציור בצורה עצלה: הדבקתי את רשימת המשתתפים בגיליון אלקטרוני, הוספתי עמודה של =RAND(), וממוין על ידי זה. זה עבד, אבל חבר שעושה סטטיסטיקה למחייתו הסתכל מעבר לכתפי ואמר, " אתה יודע שזה לא ממש אחיד, נכון?" הוא צדק, וחור הארנב שנפלתי אליו באותו ערב הוא חלק גדול מהסיבה של-Toolz יש עכשיו ראוי רשימת אקראי שעושה את הדשדוש בדרך הנכונה המדריך הזה הוא מה שלמדתי, שנכתב לכל מי שצריך לשלוף שמות מתוך כובע ורוצה שהכובע יהיה כנה.
TL;DR: אקראי רשימה או מסדר מחדש רשימה שלמה באקראי (ערבב) או שואב ממנה מדגם אקראי (בחר) הטובים משתמשים בערבוב פישר-ייטס ובמקור אקראי קריפטוגרפי כך שכל הזמנה סבירה באותה מידה השתמש בערבוב להזמנת תור ולישיבה, ובחר עבור מתנות ודוגמאות כלי זה פועל בצד הלקוח, מצייר ללא החלפה כברירת מחדל כך שהזוכים הם ייחודיים, ומסרב לצייר פריטים ייחודיים יותר ממה שהרשימה מחזיקה.
אני בונה מוצרי SaaS על Laravel ו-React, אז אכפת לי משני דברים כאן: לעשות את המתמטיקה הנכונה, ולהפוך את הממשק לברור מספיק כדי שלעולם לא תתהה אם ההגרלה הייתה הוגנת. שניהם מתבררים כחשובים יותר ממה שהם נשמעים.
מהו אקראי רשימה?
אקראי רשימה לוקח רשימה של פריטים, אחד בכל שורה, ומסדר מחדש או דוגם אותה באקראי. ערבוב הוגן הוא בעיה פתורה עם תשובה שגויה שנראית נכונה: מיון לפי מפתח אקראי מוטה, בעוד שהערבוב של פישר-ייטס לא, והדפדפן מספק את הביטים הבלתי מוטים crypto.getRandomValues(). הדבק שמות, פרסים, משימות, צוותים או רעיונות, והוא מחזיר את כל הרשימה לסדר דשדש או בוחר את מספר הזוכים שביקשת. זוהי גרסת התוכנה של ציור תלושים מקופלים מקערה, עם היתרון שהיא מסירה את ההטיה השקטה שבני אדם מציגים כשהם מנסים לבחור "אקראי" ביד.
יש באמת רק שתי פעולות, ולדעת איזו מהן אתה רוצה היא כל המיומנות. Shuffle מחזיר כל פריט שנתת לו, רק בסדר אקראי חדש, אז שום דבר לא מתווסף או אבוד. Pick מחזיר תת-קבוצה, מושך מספר מוגדר של פריטים מהמאגר. הגרלה היא בחירה. ההחלטה מי מציג ראשון בסטנדאפ היא ערבוב. רוב האנשים מגיעים לאחד הלא נכון לפחות פעם אחת, בדרך כלל מנסים " לערבב ולקחת את שלושת " המובילים; כאשר Pick עם ספירה של שלושה עושה את אותו הדבר בשלב אחד.
איך בעצם עובד דשדוש הוגן?
הנה החלק שהחבר הסטטיסטיקאי שלי הגיע אליו הטריק של הגיליון האלקטרוני, הקצאת מספר אקראי לכל שורה ומיון, מרגיש אקראי אבל לא אחיד אלגוריתמי מיון עושים השוואות, וכאשר שני מפתחות אקראיים במקרה קרובים, הטיות זעירות באופן שבו קשרים והשוואות פותרים דליפה לתוצאה ברשימות קטנות ההטיה קטנה, אבל היא אמיתית, ולכל דבר שבו הגינות היא הנקודה, "close enough" היא לא תשובה מצוינת.
השיטה הנכונה היא הדשדוש של פישר-ייטס, הנקרא לפעמים הדשדוש של Knuth לאחר שדונלד Knuth הפך את הגרסה במקום לפופולרית. זה תואר על ידי רונלד פישר ופרנק ייטס ב-1938 וקיבל את צורת המחשב המודרנית שלו על ידי ריצ'רד דורסטנפלד ב-1964. הרעיון פשוט. לכו ברשימה מהפריט האחרון לשני. בכל עמדה, בחרו אינדקס אקראי מתחילת הרשימה ועד וכולל המיקום הנוכחי, ואז החליפו את שני הפריטים. מכיוון שכל החלפה שואבת מטווח מתכווץ ומוגדר היטב, כל אחת מההזמנות האפשריות יוצאת בהסתברות שווה בדיוק. הוא פועל בזמן ליניארי, נוגע בכל פריט פעם אחת, ואינו זקוק לזיכרון נוסף מעבר לרשימה עצמה.
ה רשימת אקראי משתמש באלגוריתם זה ישירות כאשר אתה בוחר ללא החלפה, זה אותו ערבוב שהופסק מוקדם: ערבב את הרשימה, ואז קח את N הפריטים הראשונים. זה מבטיח שהזוכים יהיו שונים ושכל קבוצת זוכים אפשרית סבירה באותה מידה.
מאיפה האקראיות?
אלגוריתם הוא הוגן רק כמו המספרים האקראיים המזינים אותו אם מקור האקראיות צפוי או מוטה, דשדוש מושלם עדיין מייצר תוצאה מוטה. זה המקום שבו הדפדפן מרוויח את השמירה שלו.
דפדפנים מודרניים חושפים crypto.getRandomValues, חלק מ-W3C Web Cryptography API, הממלא מערך בערכים אקראיים חזקים מבחינה קריפטוגרפית שנלקחו ממאגר האנטרופיה של מערכת ההפעלה.That הוא מקור הרבה יותר חזק מאשר Math.random, שהוא מחולל פסאודו אקראי מהיר שמעולם לא נועד לשום דבר שבו חיזוי משנה. האקראי מעדיף crypto.getRandomValues ונופל רק בחזרה ל Math.random כאשר מקור הקריפטו באמת אינו זמין, אשר בדפדפן הנוכחי כמעט אף פעם לא.
יש עוד עדינות אחת שהייתי צריך לעשות נכון כדי להפוך מספר אקראי של 32 סיביות לאינדקס חסר פניות מ-0 ל-N מינוס 1, אתה לא יכול פשוט לקחת את השארית לאחר חלוקה ב-N, כי אלא אם כן N מתחלק באופן שווה לטווח, המדדים הנמוכים עולים מעט יותר פעמים התיקון הוא דגימת דחייה: חשב את הכפולה הגדולה ביותר של N שמתאימה לטווח, ואם תיקו נוחת מעל החתך הזה, זרוק אותו וצייר שוב זה עולה מספר זניח של הגרלות נוספות ומסיר את ההטיה לחלוטין הכלי עושה זאת על כל אינדקס שהוא בוחר, וזה סוג הפרטים שאף אחד לא שם לב עד שהוא חסר.
איך אני משתמש באקראי?
לממשק יש כפתור אחד וכמה אפשרויות. הנה איך אני מפעיל את זה.
הדבק את הרשימה שלך בתיבת הקלט, פריט אחד בכל שורה. אם העתקת תא מופרד בפסיקים מתוך גיליון אלקטרוני, העבר את מפריד הקלט לפסיק והוא יתפצל בפסיקים במקום זאת. התנהגות חיתוך ושחרור ריקה מופעלת כברירת מחדל, כך ששורות ריקות תועות ורווחים מובילים בשוגג לא יהפכו לערכי פנטום.
בחר את המצב שלך ערבב סדר מחדש הכל בחר מושך זוכים אם תבחר בחר, מופיע פאנל קטן שבו אתה מגדיר כמה לצייר והאם מותר לחזור השאר חוזר למתנה כך שכל זוכה הוא אדם אחר הפעל חוזר רק כאשר אתה באמת רוצה דגימה עם החלפה, למשל כאשר אתה מדמה הגרלות דמויות קוביות ואותו ערך יכול לחזור באופן לגיטימי.
לחץ Randomize אתה מקבל תוצאה טרי, עצמאית בכל פעם, אז אם אתה רוצה לצייר מחדש אתה פשוט לחץ שוב העתק את הפלט בלחיצה אחת כדי להדביק אותו לתוך ההכרזה שלך, הכרטיס שלך, או בכל מקום שבו התוצאה צריכה לחיות אם אתה מבקש זוכים ייחודיים יותר מאשר הרשימה יכולה לספק, הכלי אומר לך במקום להחזיר בשקט רשימה קצרה או חוזרת, וזו טעות שראיתי כלים אחרים לעשות.
בפועל, הרשימות שאני מדביק נמצאות בכל רחבי המפה יש ימים שזה עמודה של מיילים של לקוחות להגרלת פרס, בימים אחרים זה השמות בצוות שלי למי שסוקר את בקשת המשיכה הבאה, ופעם אחת זה היה כל מסעדה במרחק הליכה כי אף אחד לא יכול היה להחליט על ארוחת צהריים הכלי לא אכפת מה הפריטים, רק שהם מופרדים בצורה נקייה לכן אפשרויות הקלט שוות שנייה של תשומת לב: אם המקור שלך הוא תא גיליון אלקטרוני, מפריד הפסיק חוסך ממך עריכה ידנית, ואם זה העתק-הדבק מבולגן עם שורות ריקות, ברירת המחדל הנפתחת מנקה אותו בשקט לפני ההגרלה דקה שהושקעה בעיצוב הקלט היא דקה שאתה לא מבלה בוויכוחים אם שורה ריקה תועה נחשבת כערך.
מתי עלי לערבב ומתי לבחור?
שני המצבים מכסים עבודות שונות, והטבלה למטה היא גיליון הצ'יטים שהלוואי שהיה לי כשהתחלתי.
| אתה רוצה... | להשתמש | חוזר | למה |
|---|---|---|---|
| החליטו לדבר או להפוך סדר | לְדַשֵׁף | n/a | כולם נשארים בפנים, הסדר הוגן |
| תיקו זוכה מתנה אחת | בחר, ספר 1 | כבוי | תוצאה ייחודית יחידה |
| צייר מספר זוכי פרסים | פיק, רוזן נ | כבוי | זוכים מובהקים, ללא טבילה כפולה |
| הקצה אנשים לשני צוותים | מערבבים, ואז מפצלים | n/a | פצל את הרשימה המדשדשת לשניים |
| מדגם עם תחליף לסים | פיק, רוזן נ | על | אותו פריט עשוי לחזור על עצמו בעיצוב |
| אקראי רשימת השמעה או רשימת קריאה | לְדַשֵׁף | n/a | סדר מחדש מבלי להפיל דבר |
כלל האצבע: אם ספירת הפריטים צריכה להישאר זהה, ערבב אם אתה רוצה פחות פריטים החוצה ממה שאתה מכניס, בחר הקצאת צוות היא זו שאנשים חושבים יותר מדי ערבב את הרשימה המלאה, ואז קח את המחצית הראשונה כצוות A והשאר כצוות B, ושתי הקבוצות אקראיות ומאוזנות בגודלן.
האם זה הוגן מספיק לנהל מתנה ציבורית?
כן, והסיבה ראויה לציון ברור כי "fair" הוא כל הערך של הכלי. השילוב של דשדוש פישר-ייטס, מקור אקראי קריפטוגרפי ודגימת דחייה פירושו שלכל משתתף יש סיכוי זהה וכל קבוצה אפשרית של זוכים סבירה באותה מידה. זו ערובה חזקה יותר מאשר הגרלה פיזית, שבה גודל החלקה, קיפול ועד כמה הקערה מעורבת, כולם מציגים הטיה.
מכיוון שההגרלה פועלת כולה בדפדפן שלך, אתה יכול לעשות זאת בשידור חי על המסך במהלך זרם או פגישה, שהיא השקיפות שאנשים רוצים מהגרלה ציבורית. שום דבר לא נשלח לשרת, כך שאין שלב נסתר שבו ניתן להתעסק בתוצאה בין הקליק שלך להכרזה. אם אתה רוצה מסלול ביקורת, הקלט את ההגרלה במסך: רשימת המשתתפים גלויה, הקליק גלוי והזוכים מופיעים מיד.
הרשימה שלי פרטית?
זה חשוב יותר ממה שזה מופיע לראשונה, מכיוון שהרשימות שאנשים מבצעים באקראי לרוב אינן ציבוריות. רשימות קצרות של מועמדים, שמות צוותים פנימיים, כניסות לקוחות ורשימות דואל כולם רגישים. האקראי מעבד הכל באופן מקומי עם JavaScript רגיל. הרשימה שלך לעולם לא מועלית, נרשמת או מאוחסנת, ואתה יכול לאשר זאת בכרטיסייה רשת הדפדפן שלך, שבה לחיצה אקראית לא יורה שום בקשה. זה גם ממשיך לעבוד במצב לא מקוון לאחר טעינת הדף.
זו עמדה מכוונת בכל Toolz, וכתבתי על ההיגיון בהערה על פרטיות נתונים בכלים מקוונים. אקראי הוא דוגמה טובה למה זה חשוב: הקלט הוא לעתים קרובות רשימה של אנשים אמיתיים, ורשימה של אנשים אמיתיים היא בדיוק מסוג הדברים שאתה לא רוצה לשבת ביומן בקשות בשרת כלשהו שמעולם לא ביקרת.
כמה הרגלים שהופכים את הציור לנקי יותר
נקה את הרשימה לפני שאתה מצייר הפעל הסר כפילויות אם אדם אחד עשוי להופיע פעמיים, כך שערך כפול לא יכפיל את הסיכויים שלו בסתר. הפלת שורות ריקות מופעלת כברירת מחדל, אבל שווה להציץ כדי לוודא שלא נספרה שורה ריקה נגררת.
התאם את הספירה לפרסים במצב בחירה, הגדר את הספירה למספר המדויק של הזוכים שאתה צריך והשאר חוזר. אם יש לך שלושה פרסים, צייר שלושה בבת אחת במקום ללחוץ על הגרלה בודדת שלוש פעמים, מה שמונע מהמקרה המביך באותו שם להופיע פעמיים על פני קליקים נפרדים.
לצייר מחדש בגלוי, לא בחשאי אם זוכה אינו כשיר, להסיר אותם לצייר מחדש מול מי צופה ההגינות נובעת מהיות התהליך גלוי, לא מהתוצאה להיות סופי בלחיצה הראשונה.
שמור את זה בדפדפן כמו בכל כלי שאני שולח, עיבוד מקומי הוא ברירת המחדל כי הוא מהיר ופרטי יותר אם אתה מרכיב ערכה אישית של כלי עזר קטנים, ה מחולל מספרים אקראיים משתלב באופן טבעי עם האקראי עבור שרטוטים מספריים, והרחב יותר כלי פרודוקטיביות למפתחים roundup מסביר מדוע כדאי לבנות ארגז כלים ראשון בדפדפן.
כלים קשורים שווים הצצה
אם בחירה אקראית היא צורך חוזר, כמה שכנים יושבים בקרבת מקום. ה מחולל מספרים אקראיים מצייר מספרים בטווח עם אותה אקראיות בדרגת קריפטו, וזה מה שאתה רוצה כאשר הדבר שאתה בוחר הוא ערך ולא פריט מתוך רשימה. ה מחולל UUID מייצר מזהים ייחודיים עבור רשומות ונתוני בדיקה. ה מחולל סיסמאות מחיל את אותו מקור אקראי חזק להפקת סיסמאות מאובטחות שלושתם פועלים בדפדפן ללא הרשמה, בדיוק כמו האקראי, ואני מכסה את צד המזהה של אותה משפחה ב מדריך מחולל סיסמאות.
שאלות נפוצות
איך עובד ה-List Randomizer?
הכלי קורא את הרשימה שלך פריט אחד בכל שורה, ואז מסדר מחדש כל פריט או מושך את הזוכים שביקשת. Shuffling משתמש באלגוריתם Fisher-Yates, שעובר פעם אחת ברשימה ומחליף כל פריט במיקום קודם שנבחר באקראי, ומייצר סדר אקראי אחיד. המיקומים האקראיים מגיעים ממחולל ההצפנה של הדפדפן כך שהתוצאה היא באמת חסרת פניות.
האם האקראי באמת הוגן?
כן הוא שואב מ-crypto.getRandomValues, המקור האקראי ההצפנה המובנה בדפדפנים מודרניים, ומשתמש בדגימת דחייה כך שאין אינדקס אפילו מעט יותר סביר מאחר בשילוב עם הדשדוש של פישר-ייטס, לכל הזמנה אפשרית ברשימה שלך יש סיכוי שווה, שהוא הוגן יותר מדשדוש ידני או מיון גיליון אלקטרוני עם מפתח אקראי.
כיצד אוכל לבחור זוכה אקראי מתוך רשימת שמות?
הדבק את השמות שלך אחד בכל שורה, עבור למצב בחירה, הגדר את הספירה ל-1 ולחץ על אקראי. הכלי מחזיר שם אקראי בודד. כדי למשוך מספר זוכים בבת אחת, הגדר את הספירה גבוה יותר והשאיר את החזרות החוזרות כך שכל זוכה יהיה ייחודי.
מה ההבדל בין ערבוב לבחירה?
Shuffle מחזיר את כל הרשימה שלך בסדר אקראי חדש, כך ששום דבר לא מתווסף או הוסר, רק מסודר מחדש. Pick מחזירה תת-קבוצה, מושכת את מספר הזוכים שאתה מציין מהרשימה. השתמש ב-Shuffle להזמנת תור או ישיבה, ובחר עבור מתנות, דוגמאות, או בחר כמה אנשים מקבוצה גדולה יותר.
האם ניתן לבחור את אותו פריט יותר מפעם אחת?
רק אם אתה מפעיל חזרות כברירת מחדל, מצב בחירה מצייר ללא החלפה, כך שכל זוכה הוא פריט אחר, וזה מה שהגרלה או מתנה צריכה. הפעלת חזרות מאפשרת דגימה עם החלפה, כאשר אותו פריט יכול לעלות שוב, וזה שימושי עבור סימולציות.
למה זה לא יכול לבחור פריטים ייחודיים יותר ממה שיש ברשימה שלי?
ללא חזרות, כל זוכה חייב להיות פריט נפרד, כך שלא תוכל לצייר עשרה זוכים ייחודיים מתוך רשימה של שמונה. כשזה קורה הכלי אומר לך במקום להחזיר תוצאה שגויה. או הורד את הספירה כדי להתאים לגודל הרשימה שלך או הפעל חזרות כדי שניתן יהיה לעשות שימוש חוזר בפריטים.
האם הרשימה שלי הועלתה לשרת?
מס 'כל הניתוח והאקראי לרוץ באופן מקומי בדפדפן שלך עם JavaScript רגיל, ושום דבר לא מועבר, נרשם, או מאוחסן אתה יכול לאשר זאת בכרטיסייה רשת הדפדפן שלך, שבו לא בקשה מתבצעת כאשר אתה לוחץ על אקראי זה גם עובד במצב לא מקוון לאחר הדף נטען.
האם אני יכול להשתמש בו להגרלה או מתנה?
כן. הדבק את הנרשמים שלך אחד בכל שורה, השתמש במצב בחירה עם REPEATs מושבת, והגדר את הספירה למספר הפרסים. כל לחיצה מציירת קבוצה רעננה ועצמאית של זוכים ייחודיים. מכיוון שההגרלה היא חסרת פניות ומתרחשת בצד הלקוח, אתה יכול להפעיל אותה בשידור חי על המסך לצורך שקיפות.
