פרמוטציות

[yigael_o]

היי, מישהו יכול לתת לי קוד ב C או C++ או פסבדו קוד לפונקציה שנותנת את כל הפרמוטציות לSTRING נתון?

לדוגמה:

ABC

ABC ACB BAC BCA CAB CBA

וזה תופס גם במידה ויש AAB

ואז התשובה אמורה להיות:

AAB ABA AAB ABA BAA BAA

(כאילו למרות שזו אותה אות כל A נחשבת שונה)

[שניצל]

אפשר להתחיל מכאן:

http://en.wikipedia.org/wiki/Permutation#Algorithm_to_generate_permutations

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

חיפוש קטן בגוגל מעלה כמה תוצאות נחמדות, כמו:

http://web.usna.navy.mil/~wdj/book/node156.html

http://www.bearcave.com/random_hacks/permute.html (יש שם כמה דוגמאות ב-C)

[dvir_dotan]

פסאודו קוד הוא די פשוט, אני מניח לצורך העניין שיש לך שיטה בדוקה לבדוק את אורך המחרוזת. נניח תו סיום ם ב-C או length ב-Java.

הפונקציה הינה רקורסיבית כמובן.

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

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

אחרי החזרה היא מחליפה חזרה את התווים ועוברת לאינדקס הבא.

הינה דוגאא קצרה. נניח שנתונה המחרוזת abcd ונניח שכבר קבענו את d בתור התו הראשון ויש לנו עכשיו את המחרוזת bca.

קריאה לפונקציה עם המחרוזת dbca ומיקום 1. מכיוון שיש עוד תווים במחרוזת צריך להתפצל ותהיינה שלוש קריאות רקורסיביות:

dbca עם מיקום 2

dcba עם מיקום 2

dacb עם מיקום 2

נסתכל עכשיו בקריאה הראשונה. מכיוון שיש עוד תווים במחרוזת תהיינה שתי קריאות:

dbca עם מיקום 3

dbac עם מיקום 3

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

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

דותן