סופשבוע נעים אורח/ת
עכשיו בכלוב

היכרויות והרפתקאות

לפני 7 חודשים. 17 באפריל 2024 בשעה 20:36

אז באירועי ההיכרות שאנחנו עושות, אנחנו מחלקות את המשתתפים (כ 40) לקבוצות של כ 8-10 משתתפים, ועושות כמה משחקים כאשר בין משחק למשחק הקבוצות מתערבבות והמטרה היא לחלק את הקבוצות כך שאנשים יכירו מקסימום אנשים חדשים.

צ'אט GPT וג'מיני הבינו את הבעיה, אבל הציגו פתרונות שגויים.

עם דף ועט הצלחתי ליצור חלוקה נחמדה שנראתה על פניו לא רעה.

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

אבל ככל שקראתי על זה יותר הבנתי שמדובר בבעייה מורכבת מאוד - לפי ג'מיני יש 5775 אופציות לחלק 12 אנשים ל 3 קבוצות, ולטענתו אם יש לי 3-4 סבבי משחק שונים, זה מגיע לטריליונים. לא סופר סומכת עליו אבל אכן זה נשמע מורכב.

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

brainiacs יקרים, תגידו לי אם אני בכיוון (אין לי תואר מדעי או משהו כזה לצערי).


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

כל פעם הקוד רץ ויוצר חלוקה רנדומלית, ואז נוצר "אובייקט האובייקטים". כשהאובייקט מסיים לרוץ ולספור את כל המפגשים, אני רוצה לסכום לאורך כל האובייקט את מס' הפעמים שהערך הוא 1 (=2 אנשים נפגשו רק פעם אחת). כלומר אם אדם X פגש את אדם Y אפס פעמים זה לא טוב לי, ואם הוא פגש אותו פעמיים ומעלה זה גם לא טוב לי. כל פעם שהקוד שלי מוצא מקסימום חדש, הוא שומר את החלוקה הנוכחית. 

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


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


#דבריםשמרגשיםאותי
#אניבמקצועהלאנכון 
#רגעאיןליבעצםמקצוע


אה ואם אתם רוצים להרשם ברשימת מתעניינים לאירוע שלנו במרכז, זה https://e959.short.gy/OwI2Pz

 

Truth Seeker - לא יודע לגבי 12 אנשים, אבל פתרתי את זה ל-9 אנשים בשלושה סבבים של קבוצות בגודל 3, ול-16 אנשים בשלושה סבבים של קבוצות בגודל 4.
במקרה של תשעה אנשים:
שרטטי שריג של 3×3, עם משבצת לכל משתתף.
בהתחלה תבחרי קבוצות לפי מספר השורה. בחלוקה השניה תבחרי לפי מספר העמודה.
בסבב השלישי תבחרי לפי מספר האלכסון. ז"א, 159 הוא אלכסון, 483, ו-726.
זה יבטיח שאף אחד לא יהיה עם אותו אדם פעמיים.
הפתרון במקרה השני דומה.
לפני 7 חודשים
sweet seraphina - אקרא מחר בבוקר לעומק כי התאים כבר קצת רדומים, זה משהו שיכול להתתרגם למשהו סביב ה 40? זה צריך להיות ריבועי, נגיד 36 או 49?
לפני 7 חודשים
Truth Seeker - נשאיר משהו למחר. לילה טוב
לפני 7 חודשים
sweet seraphina - נראה שזה עובד כל עוד למספר האנשים ריבועי, מס' האנשים בקבוצה שווה לבסיס (=מס' השורות/העמודות), ויש רק 3 סבבים.
מכיוון שכאמור אני יכולה לחיות עם קצת חוסר שלמות, זה יכול להיות מספיק טוב ל usecase שלנו, גם אם לא בדיוק מתחלק ב 6 או 7 נפזר את האנשים הנוספים בין הקבוצות.
הרבה זמן לא עשיתי סודוקו :)
לפני 7 חודשים
sweet seraphina - אוקיי עכשיו התפניתי לקרוא את זה עם כמה תאי מוח פעילים והבנתי!!
לפני 7 חודשים
sweet seraphina - רגע בעצם לא נראה שזה עובד לי על 6*6... זה עובד על מס' משתתפים גדול מ 16?
לפני 7 חודשים
Truth Seeker - זה עובד על כל מספר משתתפים ריבועי. עדיין יש שלושה סבבים, אבל בכל סבב החלוקה היא ל-sqrt(n) קבוצות, כש-n זה מספר המשתתפים.

אם בכל זאת רוצים חלוקה ל-3 קבוצות, גם עם מספר כללי של משתתפים, צריך לעשות פשרות, ובאופן כללי אי אפשר לעשות שכולם יפגשו עם כולם.

פתרון אחד לזה הוא הכללה די פשוטה של מה שכתבתי: קודם לחלק את המשתתפים ל-9 "קבוצות בסיס" בגדלים מאוזנים - ז"א שכולן הן באותו הגודל עד כדי הפרש של 1 (את זה אפשר לעשות לכל מספר של משתתפים).
אז מתייחסים לכל קבוצת בסיס כאילו היא אדם אחד, מסדרים אותן על שריג של 3×3, ומשתמשים שוב בפתרון הקודם.
החסרון בפתרון הזה הוא שכל משתתף יפגוש את אנשי קבוצת הבסיס שלו שוב בסבב השני ובשלישי. מצד שני, זה מספר קטן של אנשים (בערך n/9 - 1). היתרון פה הוא שכל אחד יפגוש חלק גדול מהמשתתפים - בערך 78% - לפחות פעם אחת, ועם רובם (בערך 2/3 מהם) הוא יפגש *רק* פעם אחת.

אם ממש רוצים ללכת על האופטימום אז אפשר לנסח את זה בתור בעיית Mixed Integer Programming ולהריץ על זה solver.
לפני 7 חודשים
ויהי אור - מבחינת מספר האפשרויות דומני שאם הקבוצות בגודל שווה אז זה 12 עצרת מחולק ב 4 עצרת בחזקת 3. אם הקבוצות יכולות להיות בכל גודל, מה שלא המקרה, אבל זה נחמד, חפשי stars and bars בויקיפדיה
לפני 7 חודשים
Truth Seeker - מספר האפשרויות הוא 192599859375.
ㅤ( 12! / ( 4!^3 * 3! ) )^3
לפני 7 חודשים

להוספת תגובה לבלוג זה עליך להיות חבר/ה רשומ/ה ומחובר/ת לאתר


הרשמ/י התחבר/י