Logic required

[kinley]

Hello,
I am having trouble thinking about the logic if someone could give any hint. Please do not write code for it.
The problem is like, I am given a string say MONK and an integer say 7. So what I want is to get all possible combination of 7 letter words out of MONK so that the order is not disturbed. Since MONK is 4 letter words and I want all the 7 letter words, the extra 3 letters could be anything say underscore _ .

So the answer for the question above should be

M O N K _ _ _
M _ O _ N K _
M O N _ _ _ K
M _ _ _ O N K

Please hint me on logic. Not the code.

Thanks.

[mcleano]

Hmm if I understand you properly, I guess you could have a dictionary text file and then search all strings containing the substring "monk" ?? ... Obviously checking the length of each word also.

[kinley]

No. You have understood it wrong. As per you, I would never find a word where its M_ONK.

My problem is I want to generate new words listed above and probably more like

M _ O _ N _ K and so on.

[jsmith]

There are many more answers than you listed above.

Given MONK (4 letters) and a 7-letter word, there are quite a few possible answers.

MONK---
MON-K--
MON--K-
MON---K
MO-NK--
MO-N-K-
MO-N--K
MO--NK-
MO--N-K
MO---NK

etc. etc.

Try to find a pattern in the above solutions.

For example,

You know that the 'M' must occur in positions 1, 2, 3, or 4 (otherwise there aren't enough letters left for the O, N, and K).

When the M is in the 1st position, for example, then you know that the O must occur in positions 2, 3, 4, or 5 (for a similar reason regarding the N and K).

When the M is in the 1st position AND the O is in the 2nd position, then you know that the N must occur in positions 3, 4, 5, or 6.

etc. Now, can you generalize?

[Disch]

EDIT again: blah none of my ideas are working


I'll post again if/when I come up with something that actually works XD


EDIT yet again:

UGH

okay so I think I got it.

Starting with a smaller example, 2 letters in 5 slots. You start with all letters on the right side:
---XX

- Find the right-most X that has an empty spot to its left, and move it left
- then reset all Xs to the right of it to their starting position

--a-b  -> move b
--ab-  -> move a, reset b
-a--b  -> move b
-a-b-  -> move b
-ab--  -> move a, reset b
a---b  -> move b
a--b-
a-b--
ab---

Another example, 3/5:

--abc   -> move a, reset bc
-a-bc   -> move b, reset c
-ab-c   -> move c
-abc-   -> move a, reset bc
a--bc   -> move b, reset c
a-b-c   -> move c
a-bc-   -> move b, reset c
ab--c
ab-c-
abc--

[kinley]

Thank you guys but I don't understand your logic :-(.

Is there any other simple way?