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.
