Inserting hyphens into a string - covering all possibilities....please help!

[almurph@altavista.com]

Hi,


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


I'm nearly sure I have them all. My questions is are there any "nice"
ways of generating these patterns for any length of string longer than
4 characters.
Any comments/suggestions/code-samples much appreciated.

Thanks,
Al.

[Peter Duniho]

Re: Inserting hyphens into a string - covering all possibilities.. ..please help!

On Wed, 29 Oct 2008 10:58:54 -0700, almurph@altavis ta.com
<almurph@altavi sta.comwrote:

Hi,
>
>
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.
[...]
>
I'm nearly sure I have them all. My questions is are there any "nice"
ways of generating these patterns for any length of string longer than
4 characters.
Any comments/suggestions/code-samples much appreciated.

Well, you could do it recursively:

string[] GetHyphenatedSt rings(string strInput, int chyphen)
{
if (strInput.Lengt h <= chyphen)
{
return new string[0];
}

if (chyphen == 0)
{
return new string[] { strInput };
}

List<stringlstr Result = new List<string>();

for (int ichInsert = 1; ichInsert < strInput.Length ; ichInsert++)
{
string strHead = strInput.Substr ing(0, ichInsert) + '-',
strTail = strInput.Substr ing(ichInsert);

foreach (string strCur in GetHyphenatedSt rings(strTail,
chyphen - 1))
{
lstrResult.Add( strHead + strCur);
}
}

return lstrResult.ToAr ray();
}

Caveat: I didn't compile the above, never mind test it. But I think it's
pretty close to right, if not exactly. You call it by passing the string
and the number of hyphens you want to distribute within the string. It
returns an array of strings containing each possibility.

I have intentionally not bothered to optimize the above code. There are
numbers of opportunities to improve the performance of even the above
recursive solution, and there is a non-recursive solution that would be
even more efficient. This example in particular will spend a lot of time
allocating and garbage-collecting objects. But it has the virtue of being
reasonably simple, and so hopefully gets you pointed in the right
direction if the performance turns out to be unacceptable.

Pete

[raylopez99]

Re: Inserting hyphens into a string - covering all possibilities.. ..please help!

On Oct 29, 11:17 am, "Peter Duniho" <NpOeStPe...@nn owslpianmk.com>
wrote:

>
Caveat: I didn't compile the above, never mind test it.  But I think it's  
pretty close to right, if not exactly.
Pete

Dang you did that from memory? You're good.

RL

[almurph@altavista.com]

Re: Inserting hyphens into a string - covering all possibilities.. ..please help!

On Oct 29, 8:27 pm, raylopez99 <raylope...@yah oo.comwrote:

On Oct 29, 11:17 am, "Peter Duniho" <NpOeStPe...@nn owslpianmk.com>
wrote:
>
>
>

Caveat: I didn't compile the above, never mind test it.  But I think it's  
pretty close to right, if not exactly.
Pete

>
Dang you did that from memory? You're good.
>
RL

Peter & Jorean,

Thank you both very much for your comments. Peter - that is some of
the tightest stuff I have ever seen. Works like a charm too. Thank
you.

Al.

[Jeroen Mostert]

Re: Inserting hyphens into a string - covering all possibilities.. ..please help!

almurph@altavis ta.com wrote:

Peter & Jorean,
>

This is certainly the most creative spelling of my name I've seen yet. I
usually introduce myself as "Jerome" to English speakers, it saves a lot of
trouble... :-)


--
J.