問題描述
如何使用收益返回和遞歸獲得每個字母組合？ (How do I get every combination of letters using yield return and recursion?)
I have several lists of strings like so, from a possible list of several dozen:
1: { "A", "B", "C" }
2: { "1", "2", "3" }
3: { "D", "E", "F" }
These three were only picked as an example, and the user can pick from several dozen similar lists with varying number of elements. For another example, this is also a perfectly valid selection for a user:
25: { } // empty
4: { "%", "!", "$", "@" }
16: { "I", "a", "b", "Y" }
8: { ")", "z", "!", "8" }
What I want to do is get every combination of strings possible while keeping the 'order' of the lists. In other words, assuming we're looking at the first list, the first combination will be A1D, then A1E, then A1F, then B1D, then B1E, and so on and so forth. So far I've 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, what I get in return is this instead:
AStringGeneration.StringGenerator+<ReturnString>d__11
BStringGeneration.StringGenerator+<ReturnString>d__11
CStringGeneration.StringGenerator+<ReturnString>d__11
StringGeneration is the name of the class that ReturnString is in. When I put a breakpoint on the yield return letter + ... line, it seems to iterate through A, B, and C, but doesn't actually recurse. I'm not sure what's going on here. Can anyone explain what is wrong with my algorithm?
‑‑‑‑‑
參考解法
方法 1:
You need to enumerate the iterator:
foreach(string s in ReturnString(...)) {
Console.WriteLine(s);
}
This applies per iteration too:
foreach(string tail in ReturnString(nextList))
yield return letter + tail;
Also, I suspect you can do something with SelectMany here.
方法 2:
from x in l1
from y in l2
from z in l3
select x + y + + z
Update:
Here's an outline for an arbitrary version. I'll fill in details 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:
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 as ReturnString(lst.Where(l => l.Any()) to skip empty sequences.
(by Daniel T.、Marc Gravell、Scott Wisniewski、Grozz)