如何使用yield return和递归获取所有字母组合？

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，但实际上并没有递归。我不确定出了什么问题。有人能解释一下我的算法有什么问题吗？

- Daniel T.

---

list.Where(x => x != list.First()).ToList(); 可能可以被 list.Skip(1) 替换。 - Grozz

@Grozz 谢谢！我知道一定有更简单的方法来做这件事 :)。 - Daniel T.

Answer 1

您需要枚举迭代器:

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

这也适用于每次迭代：

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

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

- Marc Gravell

---

哎呀，我忘了提到我得到的输出正是使用你的代码枚举从ReturnString(应该是复数)返回的结果时显示的内容。另外有趣的是，在yield return letter + ...行上设置断点时，它似乎会迭代A、B和C，但实际上并不会递归到下一层级。 - Daniel T.

谢谢，看起来已经解决了！现在我只需要弄清楚为什么 :)。 - Daniel T.

我对此问题的任何可能的SelectMany解决方案都很感兴趣。我尝试理解它的工作原理，但除了非常基本的情况外，目前还超出了我的理解范围。 - Daniel T.

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

- Scott Wisniewski

---

这假设你已经了解深度了。 - Marc Gravell

抱歉，我应该提到用户可以选择的列表将是动态的。 - Daniel T.

Yield并不适用于这种情况。它无法很好地处理递归。不过，你可以通过手动编写IEnumerator实现来完成这个任务。 - Scott Wisniewski

你可以使用yield，但是你需要一个栈来维护自己的激活记录。 - Scott Wisniewski

顺便提一下，他有一个字符串列表，而不是字符。 - Grozz

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())以跳过空序列。

- Grozz

---

你的代码很好地工作，并且产生与我更新的代码相同的输出。但是，我很难理解它实际上是如何工作的，如果被要求重写它，我将无法做到。 - Daniel T.

他可以将 return matrix.First() 改为 matrix.Count() == 0，然后返回 new List<string>()。 - Daniel T.

修复了处理空列表的问题，这比较棘手。 - Grozz

请注意：字符串连接会在运行时复杂度中添加一个额外的O(N^2)项。您可能需要考虑使用链表，然后编写一个包装函数，该函数接受IEnumerable<LinkedList<char>>并将其折叠为IEnumerable<string>。 - Scott Wisniewski

顺便说一下，这个问题有点要求高效的动态规划解决方案，但我不擅长这个。 - Grozz