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

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

1 голос
/ 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 collection = new List { list1, list2, list3 };
    var answer = GetStringCombinations(collection).ToList();

    answer.ForEach(Console.WriteLine);
}

private IEnumerable<string> GetStringCombinations(List<List<string>> collection)
{
    // if the collection is empty, return null to stop the recursion
    if (!collection.Any())
    {
        yield return null;
    }
    // recurse down the list, selecting one letter each time
    else
    {
        foreach (var letter in collection.First())
        {
            // get the collection sans the first item
            var nextCollection = collection.Skip(1).ToList();

            // construct the strings using yield return and recursion
            foreach (var tail in GetStringCombinations(nextCollection))
            {
                yield return letter + tail;
            }
        }
    }
}

Однако этот код зависит от yield return для правильной работы.Как бы вы реализовали этот алгоритм без использования ключевого слова yield return, например, если бы я перенес код на ColdFusion или Ruby (при условии, что они не имеют аналогичного ключевого слова)?

Ответы [ 2 ]

1 голос
/ 31 июля 2011

Я не проверял, но должен работать 

private List<string> GetStringCombinations(List<List<string>> collection)
{
List<string> ls = new List<string>();

// if the collection is empty, return null to stop the recursion
if (!collection.Any())
{
    return null;
}
// recurse down the list, selecting one letter each time
else
{
    foreach (var letter in collection.First())
    {
        // get the collection sans the first item
        var nextCollection = collection.Skip(1).ToList();

        // construct the strings using yield return and recursion
        foreach (var tail in GetStringCombinations(nextCollection))
        {
            ls.add(letter + tail);
        }
    }
}
return ls;

}

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

псевдокод: 

  Combinations(lists[1..n], start, prefix)
   1. If start = n + 1 then print(prefix)
   2. else then
   3.    for i = 1 to lists[start].length do
   4.       Combinations(lists, start + 1, 
                prefix.append(lists[start][i])

Нечто подобное должно работать. Для достижения наилучших результатов, вызовите выше с start = самый низкий индекс массива и префикс = пустая строка. С некоторыми изменениями это будет хорошо работать.

...