How to generate as much for loops in for loop as mentioned in function?

Question

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?

This is called a "permutation"; see also https://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer — Klaus Gütter, Jun 16 '22 at 07:25

CompuChip · Accepted Answer · 2022-06-16T07:20:24.280

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)

Dmitry Bychenko · Answer 2 · 2022-06-16T07:43:46.023

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

  int count = 2;      

  var result = string.Join(Environment.NewLine, AllWords(demo, count)
    .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

Edit: If want all generated words to be unique, i.e. you want to exclude A A, B B etc. you can either add Where:

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

  int count = 2;

  var result = string.Join(Environment.NewLine, AllWords(demo, count)
    .Where(array => array.Distinct().Count() == count) 
    .Select(array => string.Join(" ", array)));

  Console.Write(result);

Or modify slightly modify AllWords:

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

  int[] indexes = new int[count];

  HashSet<int> unique = new();

  do {
    unique.Clear();

    foreach (int item in indexes)
      unique.Add(item);

    if (unique.Count == indexes.Length)
      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));
}

Output:

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

How to generate as much for loops in for loop as mentioned in function?

2 Answers2