How to get all string "possibilities"

Question

Given a string like string s = "a(b)cd(ef)", what is the best way to get a list/array containing all the following strings:

"acd",
"abcd",
"acdef",
"abcdef"

Additional information:
The order of the result doesn't matter.
The amount of parenthesis is unknown

I have tried to do this with RegEx, but didn't get very far.

This is actually a fairly simple and fun problem. however your question is likely to be closed (probably wrongly) because it has shown no code or where you are stuck. Have you attempted anything? — TheGeneral, Sep 17 '20 at 07:52
Something like [this](https://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer) might help you get started, although the answers probably don't consider optional parts. — ProgrammingLlama, Sep 17 '20 at 07:54
Does this answer your question? [Listing all permutations of a string/integer](https://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer) — Adis1102, Sep 17 '20 at 07:59
I agree with downvotes, there are likely duplicates already around. But voting to close as "too broad" is definitely wrong. @MichaelRandall, it [should not be closed](https://meta.stackoverflow.com/a/401157/1997232), but since OP mentined attempt and didn't show it, it could happen. — Sinatr, Sep 17 '20 at 08:00
@John I didn't use the word "permutation" as I was under the impression that those were just about the order of elements. — Dietrich, Sep 17 '20 at 08:48

TheGeneral · Accepted Answer · 2020-09-17T08:33:50.217

There are many ways to do this, however here is an example using a mask array to keep track of the permutation state, some regex, and a few helper methods

Given

// work out the states of the combination
public static bool GetNextState(bool[] states)
{
   for (var i = 0; i < states.Length; i++)
      if ((states[i] = !states[i]) == true)
         return false;
   return true;
}

// Create the combination
public static string Join(string[] split, string[] matches, bool[] states)
{
   var sb = new StringBuilder();
   for (var i = 0; i < states.Length; i++)
      sb.Append(split[i] + (states[i]? matches[i]:""));
   sb.Append(split.Last());
   return sb.ToString();
}

// enumerate the results
public static IEnumerable<string> Results(string input)
{
   var matches = Regex.Matches(input, @"\(.+?\)")
         .Select(x => x.Value.Trim('(', ')'))
         .ToArray();
   var split = Regex.Split(input, @"\(.+?\)");
   var states = new bool[matches.Length];

   do {
      yield return Join(split, matches, states);
   } while (!GetNextState(states));
}

Usage

string s = "a(b)cd(ef)";

foreach (var result in Results(s))
   Console.WriteLine(result);

Output

acd
abcd
acdef
abcdef

Full Demo Here

Dietrich · Answer 2 · 2020-09-17T09:35:19.277

Michael Randall's answer is correct, but after some more thinking I was finally able to come up with a (probably not very good) working solution as well

string s = "a(b)cd(ef)";
List<string> result = new List<string>();
int amount = s.Split('(').Length;
amount = (int)Math.Pow(2, amount - 1);

for (int i = 0; i < amount; i++)
{
    string temp = string.Copy(s);
    string binaryString = Convert.ToString(i, 2).PadLeft(amount, '0');
    string tempResult = "";

    for (int j = 0; j < binaryString.Length && !temp.Equals(""); j++)
    {
        Regex regex = new Regex(@"[^(]*");

        tempResult += regex.Match(temp).Value;

        if (binaryString[binaryString.Length - 1 - j].Equals('1'))
        {
            string regexStr = @"\(([^)]*)\)";
            regex = new Regex(regexStr);
            tempResult += regex.Match(temp).Value;
        }
        if (temp.Contains(')'))
            temp = temp.Substring(temp.IndexOf(')') + 1);
        else temp = "";
    }
    result.Add(tempResult.Replace("(", "").Replace(")", ""));
}

How to get all string "possibilities"

2 Answers2