How do I produce a full set of combinations with string manipulation?

Question

I have a small project where I have an input sentence where it is possible for the user to specify variations:

The {small|big} car is {red|blue}

Above is a sample sentence i want to split into 4 sentences, like this:

• The small car is red
• The big car is red
• The small car is blue
• The big car is blue

I can't seem to wrap my mind around the problem. Maybe someone can helt me pls.

Edit Here is my initial code

Regex regex = new Regex("{(.*?)}", RegexOptions.Singleline);
MatchCollection collection = regex.Matches(richTextBox1.Text);
string data = richTextBox1.Text;

//build amount of variations
foreach (Match match in collection)
{
    string[] alternatives = match.Value.Split(new char[] { '|', '{', '}' }, StringSplitOptions.RemoveEmptyEntries);
    foreach (string alternative in alternatives)
    {
        //here i get problems                  
    }
}

Answer 1

    private void ExpandString( List<string> result, string text )
    {
      var start = text.IndexOf('{');
      var end = text.IndexOf('}');
      if (start >= 0 && end > start)
      {
          var head = text.Substring(0, start);
          var list = text.Substring(start + 1, end - start - 1).Split('|');
          var tail = text.Substring(end + 1);
          foreach (var item in list)
              ExpandString(result, head + item + tail);
      }
      else
          result.Add(text);
    }

Use like:

    var result = new List<string>();
    ExpandString(result, "The {small|big} car is {red|blue}");

Answer 2

It sounds like you need a dynamic cartesian function for this. Eric Lippert's blog post written in response to Generating all Possible Combinations.

Firstly, we need to parse the input string:

Regex ex = new Regex(@"(?<=\{)(?<words>\w+(\|\w+)*)(?=\})");
var sentence = "The {small|big} car is {red|blue}";

then the input string should be modified to be used in string.Format-like functions:

int matchCount = 0;
var pattern = ex.Replace(sentence, me => 
{
    return (matchCount++).ToString(); 
});
// pattern now contains "The {0} car is {1}"

then we need to find all the matches and to apply Eric's excellent CartesianProduct extension method:

var set = ex.Matches(sentence)
    .Cast<Match>()
    .Select(m => 
        m.Groups["words"].Value
            .Split('|')
    ).CartesianProduct();

foreach (var item in set)
{
    Console.WriteLine(pattern, item.ToArray());
}

this will produce:

The small car is red
The small car is blue
The big car is red
The big car is blue

and, finally, the CartesianProduct method (taken from here):

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(
    this IEnumerable<IEnumerable<T>> sequences) 
{ 
  IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; 
  return sequences.Aggregate( 
    emptyProduct, 
    (accumulator, sequence) =>  
      from accseq in accumulator  
      from item in sequence  
      select accseq.Concat(new[] {item}));                
}

Answer 3

If you don't know the number of variations, recursion is your friend:

static public IEnumerable<string> permute(string template)
{
    List<string> options;
    string before;
    string after;
    if (FindFirstOptionList(template, out options, out before, out after))
    {
        foreach (string option in options)
        {
            foreach (string permutation in permute(before + option + after))
            {
                yield return permutation;
            }
        }
    }
    else
    {
        yield return template;
    }
}

static public bool FindFirstOptionList(string template, out List<string> options, out string before, out string after)
{
    before = string.Empty;
    after = string.Empty;
    options = new List<string>(0);
    if (template.IndexOf('{') == -1)
    {
        return false;
    }
    before = template.Substring(0, template.IndexOf('{'));
    template = template.Substring(template.IndexOf('{') + 1);
    if (template.IndexOf('}') == -1)
    {
        return false;
    }
    after = template.Substring(template.IndexOf('}') + 1);
    options = template.Substring(0, template.IndexOf('}')).Split('|').ToList();
    return true;
}

use is similar to danbystrom's solution, except this one returns an IEnumerable instead of manipulating one of the calling parameters. Beware syntax errors, etc

static void main()
{
    foreach(string permutation in permute("The {small|big} car is {red|blue}"))
    {
        Console.WriteLine(permutation);
    }
}

Answer 4

I would propose to split the input text into an ordered list of static and dynamic parts. Each dynamic part itself contains a list that stores its values and an index that represents the currently selected value. This index is intially set to zero.

To print out all possible combinations you at first have to implement a method that prints the complete list using the currently set indices of the dynamic parts. For the first call all indices will be set to zero.

Now you can increment the index of the first dynamic part and print the complete list. This will give you the first variation. Repeat this until you printed all possible values of the remaining dynamic parts.

Answer 5

Consider nesting iterative loops. Something like...

foreach(string s in someStringSet)
{
    foreach(string t in someOtherStringSet)
    {
        // do something with s and t
    }
}

Answer 6

Perhaps you are looking for this: Edited version

static void Main(string[] args)
{
    var thisstring = "The {Small|Big} car is {Red|Blue}";           
    string FirstString = thisstring.Substring(thisstring.IndexOf("{"), (thisstring.IndexOf("}") - thisstring.IndexOf("{")) + 1);
    string[] FirstPossibility = FirstString.Replace("{", "").Replace("}", "").Split('|');
    thisstring = thisstring.Replace(FirstString, "[0]");
    string SecondString = thisstring.Substring(thisstring.IndexOf("{"), (thisstring.IndexOf("}") - thisstring.IndexOf("{")) + 1);
    string[] SecondPosibility = SecondString.Replace("{", "").Replace("}", "").Split('|');
    thisstring = thisstring.Replace(SecondString, "{1}").Replace("[0]", "{0}");
    foreach (string tempFirst in FirstPossibility)
    {
        foreach (string tempSecond in SecondPosibility)
        {
            Console.WriteLine(string.Format(thisstring, tempFirst, tempSecond));
        }
    }
    Console.Read();
}

Answer 7

Something like this should work:

private void Do()
{
    string str = "The {small|big} car is {red|blue}";

    Regex regex = new Regex("{(.*?)}", RegexOptions.Singleline);

    int i = 0;
    var strWithPlaceHolders = regex.Replace(str, m => "{" + (i++).ToString() + "}");

    var collection = regex.Matches(str);

    var alternatives = collection.OfType<Match>().Select(m => m.Value.Split(new char[] { '|', '{', '}' }, StringSplitOptions.RemoveEmptyEntries));
    var replacers = GetReplacers(alternatives);

    var combinations = new List<string>();
    foreach (var replacer in replacers)
    {
        combinations.Add(string.Format(strWithPlaceHolders, replacer));
    }
}

private IEnumerable<object[]> GetReplacers(IEnumerable<string[]> alternatives)
{
    return GetAllPossibilities(0, alternatives.ToList());
}

private IEnumerable<object[]> GetAllPossibilities(int level, List<string[]> list)
{
    if (level == list.Count - 1)
    {
        foreach (var elem in list[level])
            yield return new[] { elem };
    }
    else
    {
        foreach (var elem in list[level])
        {
            var thisElemAsArray = new object[] { elem };
            foreach (var subPossibilities in GetAllPossibilities(level + 1, list))
                yield return thisElemAsArray.Concat(subPossibilities).ToArray();
        }
    }
    yield break;
}

Answer 8

string color = SomeMethodToGetColor();
string size = SomeMethodToGetSize();

string sentence = string.Format("The {0} car is {1}", size, color);