如何使用收益返回和递归获得字母的每个组合？

Question

我有几个像这样的字符串列表，可能有几十个列表：

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

这三个列表只是作为示例，用户可以从几十个具有不同数量元素的类似列表中进行选择。另一个例子，这对于用户来说也是一个完全有效的选择：

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

我想要做的是在保持列表“顺序”的同时获得可能的字符串组合。换句话说，假设我们正在查看第一个列表，第一个组合将是 A1D，然后是 A1E，然后是 A1F，然后 <代码>B1D，然后B1E，依此类推。到目前为止，我已经编写了这个递归算法：

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

但是，我得到的回报是：

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

StringGeneration 是 ReturnString 所在类的名称。当我输入在 yield return letter + ... 行上的断点，它似乎遍历 A、B 和 C，但实际上并不递归。我不确定这里发生了什么事。谁能解释一下我的算法有什么问题吗？

Answer 1

您需要枚举迭代器：

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

这也适用于每次迭代：

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

另外，我怀疑您可以在此处使用 SelectMany 做一些事情。

Answer 2

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

更新：

这是任意版本的概要。稍后我会填写详细信息。

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

Answer 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
}

调用 ReturnString(lst.Where(l => l.Any()) 来跳过空序列。