如何使用yield return和递归获得每个字母组合

本文关键字：组合 yield 何使用 return 递归 | 更新日期: 2023-09-27 18:03:59

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

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

如何使用yield return和递归获得每个字母组合

您需要枚举迭代器：

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

这也适用于每次迭代：

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

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

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

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
}

调用为CCD_ 12以跳过空序列。

相关文章：