Wondering if you can help me here. Given a string length "m" how do

you insert 3 hyphens in differing positions such that the following

conditions are met:

a. all positions are covered

b. no pattern is repeated.

For example, for a string like: ABCDEF

the solutions would be:

A-B-CDE-F

A-B-CD-EF

A-B-C-DEF

A-BCD-E-F

AB-CD-E-F

ABC-D-E-F

A-BC-DE-F

AB-C-DE-F

A-BC-D-EF

AB-C-D-EF

Since you'll want to tell a computer what to do, you have to know what

exactly it is you're trying to do. An accurate description is half the

solution. What's "covering a position"? Are the following solutions or not?

-A-B-CDEF (hyphen at the beginning)

A-B-CDEF- (hyphen at the end)

A---BCDEF (hyphens directly after each other)

--A- (special case of the abostring is less than three characters long)

--- (special case of the above: string is empty!)

We'll assume for the sake of simplicity that all of the above are allowed.

It shouldn't be hard to change things if they're not, though. In the worst

case you could produce all obvious solutions, even the ones that aren't

technically allowed, then filter those again -- it could be easier than

trying to eliminate them from the start.

Peter gave you a recursive solution that's easy to understand (if you know

recursion, that is). I want to show you another approach that's a bit

rougher around the edges, possibly more intuitive to you, which will lead us

to an (almost) completely different solution.

Let's focus on representing the problem in the most basic way possible, so

we can see relations between the solutions. If we assume that the string

cannot contain hyphens, it should be obvious that the contents of the string

don't matter: if you substitute "A" for all the letters in the above

solutions, they're still unique. All that matters is the length of the

string and where we insert our hyphens.

So we could describe our solutions as just three numbers: the positions

where we insert the hyphens. From those and the original string we can

easily produce the result. For example, "4, 6, 8" would mean hyphens at

position 4, 6 and 8, which yields "ABCD-E-F-" (starting the count from 0, of

course, as programmers do

.

Now we can try to describe our problem in these terms to see if it's

simpler. We can see that things like "0, 0, 0" and "-1, 2, 9" are not

solutions: we can't insert more than one hyphen at the same spot, and we

can't insert hyphens before the beginning of our string or after the end. So

numbers <0 and >8 won't do, and repeating numbers won't do.

This leads us to a new formulation of our problem: how do we generate all

possible combinations of three unique numbers in the range 0 through 8,

where the order doesn't matter? Generalizing this is easy: if N is the

length of our string and M is the number of hyphens, how do we generate all

possible combinations of M unique numbers in the range 0 to N + M

(exclusive), where the order doesn't matter?

Depending on how comfortable you are with numbers, this problem may be

easier to solve than the original string-based version (even though it's

really the same problem). This problem is actually a well-known one: it's

generating combinations (here "combination" is used with the specific

meaning it has in mathematics). You can easily find existing solutions to

it, but it's worth trying to solve it yourself.

For starters, you should have little trouble writing out the solutions in a

systematic way:

000 not allowed (repeats)

001 ditto

....

012 (---ABCDEF) (first actual solution)

013 (--A-BCDEF)

014 (--AB-CDEF)

015 (--ABC-DEF)

016 (--ABCD-EF)

017 (--ABCDE-F)

018 (--ABCDEF-)

020 not allowed (repeats)

021 not allowed (already had this pattern with 012)

022 not allowed (repeats)

023 (-A--BCDEF)

024 (-A-B-CDEF)

....

467 (ABCD-E--F)

468 (ABCD-E-F-)

478 (ABCD-EF--)

567 (ABCDE---F)

568 (ABCDE--F-)

578 (ABCDE-F--)

678 (ABCDEF---)

There is a pleasing and obvious regularity to this. If you can precisely

describe a way of producing just these solutions, you've got an algorithm.

Producing this set by just going over all possible candidates (000..888) and

discarding those that don't follow the rules isn't hard. This brute force

approach is not the most efficient, though. On the contrary, it quickly gets

out of hand. With M = 5 and N = 5, for example, there's a whopping 100,000

possibilities (10^5), and adding even one hyphen increases it to 1,771,561

(11^6)!

There is an algorithm that will only use as much steps as there are

solutions but that, as the textbooks are fond of saying, is left as an

exercise to the reader.

If you look at the solutions carefully and try

to think of an order that's more convenient to generate systematically, you

should be well on your way.