Need algorithm to make simple program (sentence permutations)

Question

I really cant understand how to make a simple algorithm on C# to solve my problem. So, we have a sentences:

{Hello|Hi|Hi-Hi} my {mate|m8|friend|friends}.

So, my program should make a lot of sentences looks like:

Hello my mate.
Hello my m8.
Hello my friend.
Hello my friends.
Hi my mate.
...
Hi-Hi my friends.

I know, there are a lot of programs which could do this, but i'd like to make it myself. Ofcourse, it should work with this too:

{Hello|Hi|Hi-Hi} my {mate|m8|friend|friends}, {i|we} want to {tell|say} you {hello|hi|hi-hi}.

Answer 1

As others have noted, you can solve your problem by splitting up the string into a sequence of sets, and then taking the Cartesian product of all of those sets. I wrote a bit about generating arbitrary Cartesial products here:

http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx

An alternative approach, more powerful than that, is to declare a grammar for your language and then write a program that generates every string in that language. I wrote a long series of articles on how to do so. It starts here:

http://blogs.msdn.com/b/ericlippert/archive/2010/04/26/every-program-there-is-part-one.aspx

Answer 2

Update I just wasn't too happy about my using the regexen to parse so simple input; yet I disliked the manual index manipulation jungle found in other answers.

So I replaced the tokenizing with a Enumerator-based scanner with two alternating token-states. This is more justified by the complexity of the input, and has a 'Linqy' feel to it (although it really isn't Linq). I have kept the original Regex based parser at the end of my post for interested readers.

---

This just had to be solved using Eric Lippert's/IanG's CartesianProduct Linq extension method, in which the core of the program becomes:

public static void Main(string[] args)
{
    const string data = @"{Hello|Hi|Hi-Hi} my {mate|m8|friend|friends}, {i|we} want to {tell|say} you {hello|hi|hi-hi}.";
    var pockets = Tokenize(data.GetEnumerator());

    foreach (var result in CartesianProduct(pockets))
        Console.WriteLine(string.Join("", result.ToArray()));
}

Using just two regexen (chunks and legs) to do the parsing into 'pockets', it becomes a matter of writing the CartesianProduct to the console :) Here is the full working code (.NET 3.5+):

using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Linq;
using System.Collections.Generic;

namespace X 
{ 
    static class Y 
    {
        private static bool ReadTill(this IEnumerator<char> input, string stopChars, Action<StringBuilder> action)
        {
            var sb = new StringBuilder();

            try 
            {
                while (input.MoveNext())
                    if (stopChars.Contains(input.Current))
                        return true;
                    else
                        sb.Append(input.Current);
            } finally 
            {
                action(sb);
            }

            return false;
        }


        private static IEnumerable<IEnumerable<string>> Tokenize(IEnumerator<char> input)
        {
            var result = new List<IEnumerable<string>>();

            while(input.ReadTill("{", sb => result.Add(new [] { sb.ToString() })) &&
                  input.ReadTill("}", sb => result.Add(sb.ToString().Split('|')))) 
            {
                // Console.WriteLine("Expected cumulative results: " + result.Select(a => a.Count()).Aggregate(1, (i,j) => i*j));
            }

            return result;
        }

        public static void Main(string[] args)
        {
            const string data = @"{Hello|Hi|Hi-Hi} my {mate|m8|friend|friends}, {i|we} want to {tell|say} you {hello|hi|hi-hi}.";
            var pockets = Tokenize(data.GetEnumerator());

            foreach (var result in CartesianProduct(pockets))
                Console.WriteLine(string.Join("", result.ToArray()));
        }

        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}));                
        }
    }
}

---

Old Regex based parsing:

static readonly Regex chunks = new Regex(@"^(?<chunk>{.*?}|.*?(?={|$))+$", RegexOptions.Compiled);
static readonly Regex legs = new Regex(@"^{((?<alternative>.*?)[\|}])+(?<=})$", RegexOptions.Compiled);

private static IEnumerable<String> All(this Regex regex, string text, string group)
{
    return !regex.IsMatch(text) 
                ? new [] { text } 
                : regex.Match(text).Groups[group].Captures.Cast<Capture>().Select(c => c.Value);
}

public static void Main(string[] args)
{
    const string data = @"{Hello|Hi|Hi-Hi} my {mate|m8|friend|friends}, {i|we} want to {tell|say} you {hello|hi|hi-hi}.";
    var pockets = chunks.All(data, "chunk").Select(v => legs.All(v, "alternative"));

The rest is unchanged

Answer 3

This doesn't look trivial. You need to
1. do some parsing, to extract all the lists of words that you want to combine,
2. obtain all the actual combinations of these words (which is made harder by the fact that the number of lists you want to combine is not fixed)
3. rebuild the original sentence putting all the combinations in the place of the group they came from

part 1 (the parsing part) is probably the easiest: it could be done with a Regex like this

    // get all the text within {} pairs
    var pattern = @"\{(.*?)\}";
    var query = "{Hello|Hi|Hi-Hi} my {mate|m8|friend|friends}.";
    var matches = Regex.Matches(query, pattern);

    // create a List of Lists
    for(int i=0; i< matches.Count; i++)
    {
        var nl = matches[i].Groups[1].ToString().Split('|').ToList();
        lists.Add(nl);
        // build a "template" string like "{0} my {1}"
        query = query.Replace(matches[i].Groups[1].ToString(), i.ToString());
    }

for part 2 (taking a List of Lists and obtain all resulting combinations) you can refer to this answer

for part 3 (rebuilding your original sentence) you can now take the "template" string you have in query and use String.Format to substitute all the {0}, {1} .... with the combined values from part 2

// just one example, 
// you will need to loop through all the combinations obtained from part 2    
var OneResultingCombination = new List<string>() {"hi", "mate"};
var oneResult = string.Format(query, OneResultingCombination.ToArray());

Answer 4

You can use a Tuple to hold index values of each collection.

For example, you would have something like:

List<string> Greetings = new List<string>()
{
    "Hello",
    "Hi",
    "Hallo"
};

List<string> Targets = new List<string>()
{
    "Mate",
    "m8",
    "friend",
    "friends"
};

So now you have your greetings, let's create random numbers and fetch items.

static void Main(string[] args)
{
    List<string> Greetings = new List<string>()
    {
        "Hello",
        "Hi",
        "Hallo"
    };

    List<string> Targets = new List<string>()
    {
        "Mate",
        "m8",
        "friend",
        "friends"
    };

    var combinations = new List<Tuple<int, int>>();

    Random random = new Random();

    //Say you want 5 unique combinations.
    while (combinations.Count < 6)
    {
        Tuple<int, int> tmpCombination = new Tuple<int, int>(random.Next(Greetings.Count), random.Next(Targets.Count));

        if (!combinations.Contains(tmpCombination))
        {
            combinations.Add(tmpCombination);
        }
    }

    foreach (var item in combinations)
    {
        Console.WriteLine("{0} my {1}", Greetings[item.Item1], Targets[item.Item2]);
    }

    Console.ReadKey();
}

Answer 5

Not sure what you need Linq (@user568262) or "simple" recursion (@Azad Salahli) for. Here's my take on it:

using System;
using System.Text;

class Program
{
    static Random rng = new Random();

    static string GetChoiceTemplatingResult(string t)
    {
        StringBuilder res = new StringBuilder();

        for (int i = 0; i < t.Length; ++i)
            if (t[i] == '{')
            {
                int j;
                for (j = i + 1; j < t.Length; ++j)
                    if (t[j] == '}')
                    {
                        if (j - i < 1) continue;
                        var choices = t.Substring(i + 1, j - i - 1).Split('|');
                        res.Append(choices[rng.Next(choices.Length)]);
                        i = j;
                        break;
                    }
                if (j == t.Length)
                    throw new InvalidOperationException("No matching } found.");
            }
            else
                res.Append(t[i]);

        return res.ToString();
    }

    static void Main(string[] args)
    {
        Console.WriteLine(GetChoiceTemplatingResult(
            "{Hello|Hi|Hi-Hi} my {mate|m8|friend|friends}, {i|we} want to {tell|say} you {hello|hi|hi-hi}."));
    }
}