Geek Answers Handbook

How to get each letter combination using yield return and recursion?

I have several lists of such lines, from a possible list of several tens:

1: { "A", "B", "C" } 2: { "1", "2", "3" } 3: { "D", "E", "F" }

These three were selected only as an example, and the user can choose from several dozen similar lists with a different number of elements. For another example, this is also a perfectly valid choice for the user:

 25: { } // empty 4: { "%", "!", "$", "@" } 16: { "I", "a", "b", "Y" } 8: { ")", "z", "!", "8" }

I want to make every possible combination of strings, keeping the "order" of the lists. In other words, if we look at the first list, the first combination will be A1D , then A1E , then A1F , then B1D , then B1E , etc. Etc. So far I have written this recursive algorithm:

 public void Tester() { var 2dList = new List { list1, list2, list3 }; var answer = ReturnString(2dList).ToList(); answer.ForEach(Console.WriteLine); } public IEnumerable<string> ReturnString(List<List<string>> list) { if (!list.Any()) { yield return null; } else { // for each letter in the top-most list... foreach (var letter in list.First()) { // get the remaining lists minus the first one var nextList = list.Where(x => x != list.First()).ToList(); // get the letter and recurse down to find the next yield return letter + ReturnString(nextList); } } }

However, I get this in return:

 AStringGeneration.StringGenerator+<ReturnString>d__11 BStringGeneration.StringGenerator+<ReturnString>d__11 CStringGeneration.StringGenerator+<ReturnString>d__11

StringGeneration is the name of the class in which ReturnString is located. When I put a breakpoint on the yield return letter + ... , it seems to go through A , B and C , but not really recursively. I'm not sure what is going on here. Can someone explain what is wrong with my algorithm?

+4
source share
3 answers

You need to list an iterator:

 foreach(string s in ReturnString(...)) { Console.WriteLine(s); }

This also applies to iteration:

 foreach(string tail in ReturnString(nextList)) yield return letter + tail;

Also, I suspect that you can do something with SelectMany here.

+3
source 
 from x in l1 from y in l2 from z in l3 select x + y + + z

Update:

Here is a diagram for an arbitrary version. I'll write later.

 private bool m_beforeStart; private IList<IEnumerable<char>> m_lists; private Stack<IEnumerator<char>> m_enumerators; public bool MoveNext() { while (CurrentEnumerator != null && !CurrentEnumerator.MoveNext()) { RemoveLastChar(m_stringBuilder); PopEnumerator(); } if (CurrentEnumerator == null && ! m_beforeStart) { return false; } m_beforeStart = false; while (PushEnumerator()) { if (!CurrenEnumerator.MoveNext()) { ClearEnumerators(); return false; } m_stringBuilder.Append( m_currentEnumerator.Current ); } return true; } public string Current { get { return m_stringBuilder.ToString(); } } private IEnumerator<char> CurrentEnumerator { get { return m_enumerators.Count != 0 ? m_enumerators.Peek() : null; } } private void PopEnumerator() { if (m_enumerators.Count != 0) { m_enumerators.Pop(); } } private bool PushEnumerator() { if (m_enumerators.Count == m_lists.Count) { return false; } m_enumerators.Push(m_lists[m_enumerators.Count].GetEnumerator()); }
+3
source 
 public static IEnumerable<string> ReturnString(IEnumerable<IEnumerable<string>> matrix) { if (matrix.Count() == 1) return matrix.First(); return from letter in matrix.First() // foreach letter in first list let tail = matrix.Skip(1) // get tail lists let tailStrings = ReturnString(tail) // recursively build lists of endings for each tail from ending in tailStrings // foreach string in these tail endings select letter + ending; // append letter from the first list to ending }

call ReturnString(lst.Where(l => l.Any()) to skip empty sequences.

+1
source

More articles:


All Articles