מציאת כל הוריאציות האפשריות למילה מסויימת עם נקודות

[oren]

שלום רב,

הידע שלי בתכנות מועט מאוד.

רציתי לקחת מילה מסויימת (למשל: Konstantinovskiy) ולדעת מה כל הוריאציות האפשריות לכתוב את המילה עם נקודות, כך שלא תהיה כפילות.

למשל (4 דוגמאות אקראיות):

K.onstantinovskiy
Ko.nstantinovskiy
Ko.n.s.t.antinovskiy
Konstant.i.n.o.vskiy

כיצד אוכל לעשות זאת בדרך הפשוטה ביותר?

תודה רבה,

אורן.

[infer73]

אין כאן כל קשר לתכנות - זאת בעיה בקומבינטוריקה.

מנקודת מבט תכנותית - אם אין לך מושג איך למצוא את מספר האפשרויות בדרך פשוטה יחסית,

הייתי כותב תוכנית קטנה שפשוט שמה מספר רנדומלי של נקודות במיקום רנדומלי במילה,

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

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

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

את המספר המקסימלי של אפשרויות.

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

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

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

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

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

[shikasha]

זו אכן בעיה קומבינטורית ואני אנסה להסביר. (בהנחה שהבנתי נכון את הבעיה)

אם במילה יש N אותיות, יש N-1 מקומות אפשריות לשים נקודה.

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

מס' האפשרויות למס' בינארי בן N-1 ספרות הוא 2 בחזקת N-1.

[שניצל]

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

[shikasha]

הבנתי את זה, לכן הבאתי את ההקבלה למס' בינארים.

את כל האפשרויות למס' בינארי בן 2 ספרות (למשל) אני מניח שיודעים

00

01

10

11

עכשיו תחליף 0 באין נקודה ו-1 ביש נקודה וקיבלת את כל הווריאציות.

איך לממש בדיוק זו כבר החלטה שלך.

תחשוב איך היית מממש תוכנית שיוצרת סטרינגים של כל המס' הבינארים בני N ספרות, לא שונה הרבה.

[oren]

אני באמת צריך רק את הוריאציות עצמן ולצערי לא ממש הבנתי את אשר כתבתם.

אתן דוגמה, למשל, הנה כל הוריאציות (אני מקווה...) שאפשר לעשות עם המילה oren:

o.ren
or.en
ore.n
o.r.en
or.e.n
o.r.e.n
o.re.n

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

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

אודה מאוד לעזרה בנדון.

תודה והמשך יום נעים,

אורן.

[user57202]

הבעיה שלך שקולה למציאת כל תתי הקבוצות של קבוצה מסויימת

http://stackoverflow.com/questions/728972/finding-all-the-subsets-of-a-set

יש פה דיון בנושא

[Zelig]

מה אורך רצף הנקודות הארוך ביותר? אם מותר יותר מנקודה אחת ברצף, אז הבעיה לא לגמרי שקולה.

[oren]

שאלה מעולה

כרגע אסור יותר מנקודה אחת ברצף.

אך באמת הכיוון הוא לקבל פלט של כל הוריאציות שאפשר עם נקודה אחת (בלי 2 ברצף וכו') ולאחר מכן עם אפשרות ל- 2 נקודות ברצף, 3 ברצף וכן הלאה.

השאלה, איך עושים את זה בפשטות?

כמו שכתבתי, אין לי ידע רב בתכנות והלינק שנכנסתי אליו בהמלצת user57202 לא ממש עזר לי להבין :s05:

רב תודות לכם,

אורן.

[שניצל]

נניח שיש לך מילה באורך 6 אותיות.

אז יש 5 מקומות אפשריים לשים נקודה.

בכל מקום כזה או שיש נקודה (נקרא למצב כזה "0") או שאין נקודה (נקרא למצב כזה "1").

אז לכל וריאציה אתה יכול להתאים מחרוזת בינארית (כלומר, של אפסים ואחדות) באורך 10. נניח, לוריאציה הזו:

a.bc.d.ef

מתאים הרצף 10110.

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

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

יש מבין?

(יש כמובן פתרונות אחרים, לדוגמה רקורסיה)

[oren]

מעולה, הבנתי!

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

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

השאלה אם אין כבר תוכנה כזו, או איזה Notepad משוכלל שיודע לעשות זאת, או אולי ב- Exel? במקום לבנות תוכנה כזו...

יש רעיון/כיוון?

תודה,

אורן.

[שניצל]

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