I'm trying to generate all possible word combinations using a List<string>. For example, if I want to generate all possible word combinations of 2, the function would look like this:

public static List<string> GenerateWordsOf2(List<string> uniqueWords)
{
    List<string> unique2Words = new();
    for (int i = 0; i < uniqueWords.Count; i  )
    {
        for (int j = 0; j < uniqueWords.Count; j  )
        {
            if (i != j)
            {
                unique2Words.Add(uniqueWords[i]   " "   uniqueWords[j]);
            }
        }
    }
    return unique2Words;
}

This works as expected, but I when I want to generate, for example, unique words of 3, I would need to write a new function for that, making another loop inside it. Is there, maybe, a more effective way of doing this, like making a function that would take a number and generate that much of unique words list?

CodePudding user response：

You can do this iteratively, with a single for loop, as follows.

• Start with a list containing only the "empty sentence".
• In each step, add each word to each previously constructed sentence.

Suppose uniqueWords is "a", "b", "c".

• At the start, you will have {""}.
• After the first step, you will have {"a", "b", "c"}
• After the second step, you will have { "a a", "a b", "a c", "b a", "b b", "b c", "c a", "c b", "c c"}
• After the third step, you will get { "a a a", "a b a", ... }

The only modification required is then to filter out duplicates. This leads to something like this (unoptimized) example:

using System; using System.Collections.Generic;

public class SentenceGenerator
{
    public static List<List<string>> ExpandSentences(List<List<string>> partialSentences, List<string> uniqueWords)
    {
        var newSentences = new List<List<string>>();
        foreach(var sentence in partialSentences)
        {
            foreach(var word in uniqueWords)
            {
                if(sentence.Contains(word))
                {
                    continue;
                }
                
                // Make a copy of the old sentence
                var newSentence = new List<string>(sentence);
            
                // Add a new word
                newSentence.Add(word);
                
                newSentences.Add(newSentence);
            }
        }
        
        return newSentences;
    }
    
    public static void Main()
    {
        var uniqueWords = new List<string>() {
            "hello",
            "beautiful",
            "world", 
            "full",
            "of",
            "people" };
        
        var sentences = new List<List<string>>() { 
            // Start with an empty sentence
            new List<string>() 
        };
        
        for(int i = 1; i <= 3; i  )
        {
            sentences = ExpandSentences(sentences, uniqueWords);
        }
        
        System.Console.WriteLine("Generated "   sentences.Count   " sentences.");
        foreach(var sentence in sentences)
        {
            System.Console.WriteLine(string.Join(" ", sentence));
        }
    }
}

Run it online (IDEOne)

CodePudding user response：

If you want to get, say, all combinations of 3 items, you can keep array indexes where you can put which items to take:

uniqueWords = {'A', 'B', 'C', 'D'}

indexes = {0, 0, 0} // AAA
indexes = {0, 0, 1} // AAB
indexes = {0, 0, 2} // AAC
indexes = {0, 1, 0} // ABA
...
indexes = {2, 2, 2} // CCC

Code: (let's implement it in general case, with IEnumerable<T> as an input argument)

using System.Linq;

...

private static IEnumerable<T[]> AllWords<T>(IEnumerable<T> uniqueWords, int count) {
  T[] words = uniqueWords.ToArray();

  int[] indexes = new int[count];

  do {
    yield return indexes.Select(index => words[index]).ToArray();

    for (int i = indexes.Length - 1; i >= 0; --i)
      if (  indexes[i] >= words.Length)
        indexes[i] = 0;
      else
        break;
  }
  while (!indexes.All(index => index == 0));
}

Demo:

  List<char> demo = new List<char>() { 'A', 'B', 'C', 'D' };

  var result = string.Join(Environment.NewLine, AllWords(demo, 2)
    .Select(array => string.Join(" ", array)));

  Console.Write(result);

Output:

A A
A B
A C
A D
B A
B B
B C
B D
C A
C B
C C
C D
D A
D B
D C
D D