Как мне получить каждую комбинацию букв, используя возвращение и рекурсию? - PullRequest
Новая
       17

Как мне получить каждую комбинацию букв, используя возвращение и рекурсию?

4 голосов
/ 31 июля 2011

У меня есть несколько списков строк, например, из возможного списка из нескольких десятков: 

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, но фактически не рекурсивно.Я не уверен, что здесь происходит.Кто-нибудь может объяснить, что не так с моим алгоритмом?

Ответы [ 3 ]

3 голосов
/ 31 июля 2011 
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());
}
3 голосов
/ 31 июля 2011

Вам нужно перечислить итератор: 

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

Это относится и к каждой итерации: 

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

Кроме того, я подозреваю, что вы можете сделать что-то с SelectMany здесь.

1 голос
/ 31 июля 2011 
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()), чтобы пропустить пустые последовательности.

...