Как перебирать списки разной длины, чтобы найти все перестановки?

Это не должно быть слишком сложно, но у меня, кажется, переполнение стека (huehue). У меня есть серия списков, и я хочу найти все перестановки, в которых они могут быть упорядочены. Все списки имеют разную длину.

Например:

Список 1: 1

Список 2: 1, 2

Все перестановки будут:

1, 1

1, 2

В моем случае я не переключаю числа. (Например, 2, 1) Какой самый простой способ написать это?

 Matthew Watson31 июл. 2016 г., 12:18
 Emric Månsson31 июл. 2016 г., 10:56
@Enigmativity Как вы проиллюстрировали со списком ABC и 12. Но в основном с большим количеством списков. Пример: AB, 12 и $%. A1 $, A1%, A2 $, A2% и так далее.
 Enigmativity31 июл. 2016 г., 09:59
Что вы подразумеваете под серией списков? Ваш пример показывает только два. У вас есть только два или у вас есть еще? Вы после декартового произведения всех списков?
 Emric Månsson31 июл. 2016 г., 10:32
Это верно, я имею в виду комбинации с несколькими списками. Представь себе велосипедный замок. Извините за то, что неясно.
 Matthew Watson31 июл. 2016 г., 10:12
Вы имеете в виду перестановки? Или, может быть, вы действительно имеете в виду комбинации (иначе как декартово произведение)? Комбинации двух списков ABC и 12 будут A1, B1, C1, A2, B2, C2
 Enigmativity31 июл. 2016 г., 10:47
@ EmricMånsson - Извините, но это делает его еще менее понятным. Как вы получаете комбинации с несколькими списками?
 user652277331 июл. 2016 г., 09:54

Ответы на вопрос(3)

Решение Вопроса

Я не могу сказать, является ли следующий способ самым простым, но IMO - самый эффективный. Это в основном обобщенная версия моего ответа наГлядя на каждую комбинацию в неровном массиве:

public static class Algorithms
{
    public static IEnumerable<T[]> GenerateCombinations<T>(this IReadOnlyList<IReadOnlyList<T>> input)
    {
        var result = new T[input.Count];
        var indices = new int[input.Count];
        for (int pos = 0, index = 0; ;)
        {
            for (; pos < result.Length; pos++, index = 0)
            {
                indices[pos] = index;
                result[pos] = input[pos][index];
            }
            yield return result;
            do
            {
                if (pos == 0) yield break;
                index = indices[--pos] + 1;
            }
            while (index >= input[pos].Count);
        }
    }
}

Вы можете увидеть объяснение в связанном ответе (вскоре это эмуляция вложенных циклов). Кроме того, поскольку по соображениям производительности он создает внутренний буфер без клонирования, его необходимо клонировать, если вы хотите сохранить результат для последующей обработки.

Пример использования:

var list1 = new List<int> { 1 };
var list2 = new List<int> { 1, 2 };
var lists = new[] { list1, list2 };

// Non caching usage
foreach (var combination in lists.GenerateCombinations())
{
    // do something with the combination
}

// Caching usage
var combinations = lists.GenerateCombinations().Select(c => c.ToList()).ToList();

ОБНОВИТЬ: GenerateCombinations это стандартный C #итератор метод, и реализация в основном эмулируетN вложенные циклы (гдеN этоinput.Count) вот так (в псевдокоде):

для (Int I0 = 0; я0 <input [0] .Count; я0++)
для (Int I1 = 0; я1 <input [1] .Count; я1++)
для (Int I2 = 0; я2 <input [2] .Count; я2++)
...
для (Int IN-1 = 0; яN-1 <input [N-1] .Count; яN-1++)
yield {input [0] [i0], вход [1] [i1], вход [2] [i2], ..., вход [N-1] [iN-1]}

или показывая это по-другому:

for (indices[0] = 0; indices[0] < input[0].Count; indices[0]++)
{
    result[0] = input[0][indices[0]];
    for (indices[1] = 0; indices[1] < input[1].Count; indices[1]++)
    {
        result[1] = input[1][indices[1]];
        // ...
        for (indices[N-1] = 0; indices[N-1] < input[N-1].Count; indices[N-1]++)
        {
            result[N-1] = input[N-1][indices[N-1]];
            yield return result;
        }
    }
}
 Emric Månsson31 июл. 2016 г., 18:55
Итак, я все еще не до конца понимаю код (также прочитайте ответ из другого поста). ._. Если вам так хочется, я был бы очень признателен за объяснение происходящего. Я прочитал немного о IEnumerables, но все еще не могу обернуть голову вокруг этого.
 Ivan Stoev31 июл. 2016 г., 12:38
Добро пожаловать. Я не был уверен, что вам нужно решение или понимание того, как его реализовать, поэтому я предположил первое, иначе, вероятно, сосредоточился бы больше на объяснении.
 Emric Månsson31 июл. 2016 г., 12:14
Спасибо за ответ! Это похоже на очень правильное решение. Однако я вроде как новичок в IEnumerables и необязательных значениях цикла for. Я вернусь через пару часов, когда пойму код и выскажу ваш ответ. : D

Попробуй это:

Func<IEnumerable<string>, IEnumerable<string>> combine = null;
combine = xs =>
    xs.Skip(1).Any()
    ? xs.First().SelectMany(x => combine(xs.Skip(1)), (x, y) => String.Format("{0}{1}", x, y))
    : xs.First().Select(x => x.ToString());

var strings = new [] { "AB", "12", "$%" };

foreach (var x in combine(strings))
{
    Console.WriteLine(x);
}

Это дает мне:

A1$
A1%
A2$
A2%
B1$
B1%
B2$
B2%

Вложенные циклы:

List<int> listA = (whatever), listB = (whatever);
var answers = new List<Tuple<int,int>>;
for(int a in listA)
    for(int b in listB)
        answers.add(Tuple.create(a,b));
// do whatever with answers
 Ori Refael31 июл. 2016 г., 10:32
для неупорядоченных групп (серий) это нормально ..
 Emric Månsson31 июл. 2016 г., 11:13
Это почти правильно. Однако в моем случае я могу получить 40 списков разной длины. Я прочитал документацию по кортежам, и вы можете сделать кортежи 8 размеров. Скорее всего, я мог бы легко объединить список из целых чисел a и b, но я не знаю, как бы получить ~ 40 вложенных для циклов? Есть ли рекурсивное решение?

Ваш ответ на вопрос