Find all possible combinations of word with and without hyphens

Question

For a string that may have zero or more hyphens in it, I need to extract all the different possibilities with and without hyphens.

For example, the string "A-B" would result in "A-B" and "AB" (two possibilities).

The string "A-B-C" would result in "A-B-C", "AB-C", "A-BC" and "ABC" (four possibilities).

The string "A-B-C-D" would result in "A-B-C-D", "AB-C-D", "A-BC-D", "A-B-CD", "AB-CD", "ABC-D", "A-BCD" and "ABCD" (eight possibilities).

...etc, etc.

I've experimented with some nested loops but haven't been able to get anywhere near the desired result. I suspect I need something recursive unless there is some simple solution I am overlooking.

NB. This is to build a SQL query (shame that SQL Server does't have MySQL's REGEXP pattern matching).

Here is one attempt I was working on. This might work if I do this recursively.

string keyword = "A-B-C-D";

List<int> hyphens = new List<int>();

int pos = keyword.IndexOf('-');
while (pos != -1)
{
    hyphens.Add(pos);
    pos = keyword.IndexOf('-', pos + 1);
}

for (int i = 0; i < hyphens.Count(); i++)
{
    string result = keyword.Substring(0, hyphens[i]) + keyword.Substring(hyphens[i] + 1);

    Response.Write("<p>" + result);
}

A B C D are words of varying length.

Answer 1

Take a look at your sample cases. Have you noticed a pattern?

• With 1 hyphen there are 2 possibilities.
• With 2 hyphens there are 4 possibilities.
• With 3 hyphens there are 8 possibilities.

The number of possibilities is 2ⁿ.

This is literally exponential growth, so if there are too many hyphens in the string, it will quickly become infeasible to print them all. (With just 30 hyphens there are over a billion combinations!)

That said, for smaller numbers of hyphens it might be interesting to generate a list. To do this, you can think of each hyphen as a bit in a binary number. If the bit is 1, the hyphen is present, otherwise it is not. So this suggests a fairly straightforward solution:

1. Split the original string on the hyphens
2. Let n = the number of hyphens
3. Count from 2ⁿ - 1 down to 0. Treat this counter as a bitmask.
4. For each count begin building a string starting with the first part.
5. Concatenate each of the remaining parts to the string in order, preceded by a hyphen only if the corresponding bit in the bitmask is set.
6. Add the resulting string to the output and continue until the counter is exhausted.

Translated to code we have:

public static IEnumerable<string> EnumerateHyphenatedStrings(string s)
{
    string[] parts = s.Split('-');
    int n = parts.Length - 1;
    if (n > 30) throw new Exception("too many hyphens");
    for (int m = (1 << n) - 1; m >= 0; m--)
    {
        StringBuilder sb = new StringBuilder(parts[0]);
        for (int i = 1; i <= n; i++)
        {
            if ((m & (1 << (i - 1))) > 0) sb.Append('-');
            sb.Append(parts[i]);
        }
        yield return sb.ToString();
    }
}

Fiddle: https://dotnetfiddle.net/ne3N8f

Answer 2

You should be able to track each hyphen position, and basically say its either there or not there. Loop through all the combinations, and you got all your strings. I found the easiest way to track it was using a binary, since its easy to add those with Convert.ToInt32

I came up with this:

string keyword = "A-B-C-D";
string[] keywordSplit = keyword.Split('-');
int combinations = Convert.ToInt32(Math.Pow(2.0, keywordSplit.Length - 1.0));

List<string> results = new List<string>();

for (int j = 0; j < combinations; j++)
{
    string result = "";
    string hyphenAdded = Convert.ToString(j, 2).PadLeft(keywordSplit.Length - 1, '0');
    // Generate string
    for (int i = 0; i < keywordSplit.Length; i++)
    {
        result += keywordSplit[i] +
                  ((i < keywordSplit.Length - 1) && (hyphenAdded[i].Equals('1')) ? "-" : "");
    }
    results.Add(result);
}