עזרה

[pilot23]

עזרה

שלום,
אני רוצה לכתוב פונקציה רקורסיבית , אשר מקבלת כפרמטר מספר שלם N ועוד פרמטרים נוספים (אם צריך) ומדפיסה את כל הפרמוטציות של המספרים מ-1 עד N. למשל עבור 4.
חשבתי כמובן אם לעשות איזשהו מערך שמבקש מהמשתמש את ה- size שהוא רוצה.. ואז להשתמש בפונקציית swap כדי כל הזמן להחליף את הערכים. העניין הוא שאני לא בטוחה איך אני אמורה להשתמש כאן בפונקציית swap כדי כל הזמן לשנות את הערכים לכל הווריאציות האפשרויות.
אשמח לשמוע את דעתכם.

תודה.

 

[KingUnique]

בבקשה

 

[Guy Yafe]

עצה לפיתרון

כל הפרמוטציות האפשריות של מספרים מ-1 עד N הן איחוד של כל הפרמוטציות בגודל N-1 של מספרים מ-1 עד N ללא מספר כלשהו i בתוספת המספר i:
הכניסי את כל המספרים מ-1 עד N למערך בגודל N
הפונקציה שלך תרוץ בלולאת FOR על המערך:
עבור כל i החליפי באמצעות SWAP את האיבר הראשון עם האיבר ה-i-י במערך וקראי מחדש לפונקציה עם תת המערך ללא האיבר הראשון.

 

[pilot23]

לגיא

תודה רבה על העזרה .
כמה דברים :
כתבת " הפרמוטציות האפשריות של מספרים מ-1 עד N הן איחוד של כל הפרמוטציות בגודל N-1 "... למה N-1 ?

אתה יכול להמחיש לי ע"י דוגמא בצורה מספרית את מה שכתבת בשורה האחרונה... ? לא ממש הבנתי, קודם כל איך אני מציינת את המספר הראשון , כלומר האיבר במקום ה- 0 ? ולמה אני עושה את ההחלפה הזו של האיבר הראשון עם האיבר ה- iי ? מה זה נותן לי ?
ואיך אני קוראת לפונקציה עם תת מערך ללא האיבר הראשון ?

 

[Guy Yafe]

תשובה

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

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

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

 

[pilot23]

בעיה

עכשיו נודע לי שאני לא יכולה להשתמש בפונקציות חיצוניות. איך אוכל לפתור את הבעיה עם swap ?

 

[Guy Yafe]

תכתבי את swap בעצמך

http://lmgtfy.com/?q=c+swap+two+numbers