שאלה על פרמוטציות

[clocker]

שאלה על פרמוטציות

ברצוני לכתוב פונקציה בשם Permutation, שמקבלת 3 פרמטרים 1. מספר טבעי n 2. מספר בין 1 לn עצרת המייצג את הפרמוטציה (נקרא לו אינדקס הפרמוטציה i) 3. מספר בין 1 לn המייצג את המקום הn בפרמוטציה (נקרא לו k) לדוגמא, נניח וn=3 אז הפרמוטציות הן 1. 321 2. 312 3. 213 4. 231 5. 132 6. 123 הערך של הפונקציה Permutation עבור k=2 ו i=5 הוא 3 (העמודה השניה, בשורה החמישית) הערה חשובה מאוד: לא חשוב לי איזה פרמוטציה מקבלת איזה אינדקס, כל עוד כל הפרמוטציות נמצאות שם

 

[vinney]

שכחת את השאלה ../images/Emo13.gif

 

[clocker]

השאלה היא "כיצד" כמובן, ../images/Emo13.gif

השאלה היא: "כיצד" אם בכלל הדבר אפשרי זה נראה לי כמו משהו פשוט ששוכב לו מתחת לאף שלי, אך אני לא מצליח לחשוב על דרך פשוטה שתעבוד לכל n.

 

[vinney]

אתה תמיד יכול לחשב את כל האפשרויות

ולבחור אחת אקראית, זה יהיה אקספוננציאלי. השאלה היא למה? מה המטרה שלך?

 

[clocker]

הלוואי וזה היה רק אקספוננציאלי

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

 

[vinney]

לא

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

 

[clocker]

מה הקשר ?

הסיבוכיות של Permutation לא יכולה להיות קבוע, וזה די ברור. אם הסיבוכיות של הפונקציה Permutation היא f1, אז הסיבוכיות של בניית המערך כולו הוא כn עצרת כפול f1, (n עצרת קריאות לPermutation ) וחוץ מזה, אחרי מחשבה קלה הבנתי שאפשר לבנות את המערך כולו בסיבוכיות n עצרת (גם זמן וגם מקום) אבל אני עדיין חושש שאולי אפשר לממש את הפונקציה Permutation מבלי לבנות את כל המערך.

 

[vinney]

אתה יכול לבנות עד האינקס שנדרש ממך

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

 

[clocker]

אפשר גם להתחכם, ולהקטין את סיבוכיות

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

o(log(n!))=o(n*log)​

ואם הפונקציה Permutation לא נקראה בעבר עם האינדקס הזה, אזי נבנה עוד שורה במערך בסיבוכיות o1, וניתן לשורה הזו את האינדקס הנדרש. לסיכום, אפשר להוריד את סיבוכיות הזמן ב-ה-מ-ו-ן, ולהביא אותה לnlog1 במקרה הגרוע, אבל עדיין סיבוכיות המקום תהיה n עצרת כפול n

 

[IP yuval]

חפש unranking function

זה נותן לך את 1 ו2. מכאן כבר 3 זה לא בעיה (למרות שאולי אפשר לעשות אלגוריתם יותר מהיר כאשר גם 3 דרוש). אפשר לעשות את זה באופן לינארי, ונראה לי שזה שיפור די רציני בשבילך, כך שזה אמור להספיק

.

 

[vinney]

איך זה עובד?

לא מכיר את זה, ואין לי כוח לחפש

 

[IP yuval]

אלגוריתם מאוד יפה

מאת Wendy Myrvold 1 , Frank Ruskey ∗,2.

procedure unrank1(n, r, π) if n > 0 then swap(π[n − 1], π[r mod n]); unrank1(n − 1, r/n , π); fi; end {of unrank1};​

כאשר, π הוא מערך המכיל את 0 עד n-1, כאשר זה לא ממש חשוב הסדר של המספרים (סדר שונה יתן פרמוטציות שונות). n קובע את גודל הפרמוטציה וr זה אינדקס הפרמוטציה בין 1 ל n!. אפשר להוכיח את באינדוקציה שהפונקציה על/חח"ע.

 

[yossiea]

אגב נראה לי שאפשר גם ליניארית.

אם הבנתי נכון: יש לנו מערך n של נגיד 4 איברים 0, 1, 2, 3 שאותם אנחנו רוצים לסדר בכל הפרמוטציות האפשריות ולפי מה שהבנתי השאלה היא איך מחזירים פרמוטציה כלשהי (לא חשוב איזו) בהתאם לאינדקס כלשהו (שרץ על כל העצרת של n במקרה הזה 0 עד 24). הרעיון הוא בלי להיכנס ללולאה פשוט להמיר את האינדקס i למספר "בבסיס משתנה", כלומר במקרה שלנו: האינדקס 7 = 0, 0, 2, 0 האינדקס 14 = 0, 1, 0, 3 את המספר הזה אפשר להפוך לפרמוטציה ייחודית בלולאה של n (כלומר 4) זה שולי ביחס לעצרת של n. רק שאני מנסה לכתוב קוד פשוט שממיר את האינדקס למספר בבסיס משתנה ואח"כ לפרמוטציה אצלי זה עובד כרגע בלולאה. אבל לדעתי זה לא צריך להיות כזה מסובך לכתוב משהו שמחשב את זה ישירות ללא לולאה. אני מקווה שהובנתי.

 

[IP yuval]

לא הבנתי, אבל האלגוריתם שהבאתי

הוא לינארי, כלומר תלוי בN.. אתה יכול לצרף את הקוד שכתבת..

 

[yossiea]

האלגוריתם שהבאת לא מומלץ...

כדאי שתקרא את המאמר שם ב-MSDN שצרפתי בהודעה השנייה ותבין למה. לא מומלץ בלשון המעטה ויש כמה סיבות טובות לכך.

 

[yossiea]

כן מצאתי...

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

for(int j = 1; j <= len; j++){ F[len - j] = k % j; k /= j; }​

אחר כך פשוט להפוך אותו לפרמוטציה ייחודית עם מערך עזר נוסף:

for(int i = 0; i < len; i++) T = ++F; N[len-1] = 1; for(int i = len - 2; i >= 0; i--){ N = T; for(int j = i + 1; j < len; j++){ if(N[j] >= N) N[j]++; } }​

הלולאה הזאת רצה על כל הפוזיציות פחות אחת ומבצעת לולאה פנימית של לכל היותר n - 1 שזה בעצם 1 + 2 + 3 + 4 + ... פעמים לפי n. טוב זה לא ממש ליניארי אבל בהחלט פולינומיאלי ולא אקספ. מקורות: http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnnetsec/html/permutations.asp ויקיפדיה אנגלית, ערכים: Mixed Radix, Factoradic

 

[IP yuval]

עדיין לא הבנתי למה אתה אומר

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

 

[ron369]

נראה לי שאתה צודק

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

 

[yossiea]

לטעמי האישי...

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

 

[ron369]

טוב, אז נהופך אותו ללא רקורסיבי,

אם זה מה שמפריע לך כל כך.