Поиск декартова произведения с помощью LINQ

Постановка вопроса: как найти декартово произведение произвольного количества последовательностей с помощью LINQ?

Для начала, давайте убедимся, что мы знаем, о чем идет речь. Я буду обозначать последовательности как упорядоченные множества: {a, b, c, d...} Декартово произведение двух последовательностей S1 и S2 есть последовательность всех возможных упорядоченных пар таких, что их первый элемент из S1, а второй — из S2. Так, к примеру, если у вас есть две последовательности {a, b} и {x, y, z}, то их декартово произведение выглядит как {{a, x}, {a, y}, {a, z}, {b, x}, {b, y}, {b, z}}.

Для упрощения, предположим, что S1 и S2 состоят из элементов одного типа. Разумеется, мы можем определить декартово произведение последовательности строк с последовательностью чисел как последовательность кортежей (string, int), но впоследствии это окажется тяжело обобщать, потому что система типов C#, в частности, не лучшим образом работает с кортежами произвольной длины.

В LINQ есть оператор специально для вычисления декартовых произведений: в «синтаксисе методов» это SelectMany, в «синтаксисе запросов» это запрос с двумя выражениями «from»:

var s1 = new[] {a, b}; <br/>
var s2 = new[] {x, y, z}; <br/>
var product =  <br/>
    from first in s1 <br/>
    from second in s2 <br/>
    select new[] { first, second };

Конечно же, мы можем обобщить декартово произведение на более чем две последовательности. Декартово произведение n последовательностей {S1, S2, ... , Sn} есть последовательность всех возможных n-элементных последовательностей, у которых первый элемент из S1, второй из S2 и т.д.

В этом определении не хватает тривиального случая: что есть декартово произведение нуля последовательностей? Пускай в таком случае оно состоит из последовательности, содержащей единственный элемент: пустую последовательность, то есть { { } }.

Обратите внимание, что это дает логичное определение декартова произведения одной последовательности. Декартово произведение последовательности, содержащей одну-единственную последовательность (скажем, {{a, b}}) есть последовательность всех возможных одноэлементых последовательностей, где первый (и единственный) элемент из {a, b}. Таким образом, декартово произведение {{a, b}} есть {{a}, {b}}.

С помощью LINQ вы можете составить декартово произведение любого количества последовательностей достаточно просто, если вы изначально знаете, с каким количеством будете работать:

var product =  <br/>
    from first in s1 <br/>
    from second in s2 <br/>
    from third in s3 <br/>
    select new[] {first, second, third};

Но что делать, если вы не знаете на этапе написания кода, сколько у вас будет последовательностей? То есть, как написать тело функции:

public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)

Что ж, есть причина использовать индукцию; эта идея практически никогда не подводит при работе с рекурсивно определенными структурами данных.

Если sequences содержит ноль последовательностей, дело сделано: мы просто возвращаем { { } }.

Как найти декартово произведение двух последовательностей, скажем, снова {a, b} и {x, y, z}? Начнем с подсчета декартова произведения первой последовательности. Пускай индуктивное предположение состоит в том, что мы каким-либо образом сделали это, так что мы знаем ответ: {{a}, {b}}. Как соединить {{a}, {b}} с {x, y, z}, чтобы получить общее произведение?

Давайте вернемся в поисках вдохновения к изначальному определению декартова произведения двух последовательностей. Декартово произведение {{a}, {b}} и {x, y, z} — беспорядочное {{{a}, x}, {{a}, y}, {{a}, z}, {{b}, x}, {{b}, y}, {{b},z}}, которое, тем не менее, соблазнительно близко к тому, что мы хотим получить. Мы не просто хотим найти декартово произведение {{a}, {b}} и {x, y, z}, создавая последовательность, содержащую {a} и x, но нет, вместо этого нам нужно вычислить декартово произведение, присоединяя x к {a}, чтобы получить {a, x}! Другими словами, конкатенируя {a} и {x}.

В терминах кода: пускай у нас есть старое декартово произведение, скажем {{a}, {b}}. Мы хотим соединить его с последовательностью {x, y, z}:

var newProduct =  <br/>
    from old in oldProduct <br/>
    from item in sequence <br/>
    select old.Concat(new[]{item}};

И теперь у нас есть благополучный индукционный переход. Если oldProduct — любое декартово произведение, то мы можем вычислить его комбинацию с другой последовательностью, чтобы получить новое декартово произведение.

На всякий пожарный: этот метод работает с основой индукции? Да. Если мы хотим скомбинировать декартово произведение { { } } с последовательностью {{a}, {b}}, мы склеиваем { } с {a} и { } с {b}, чтобы получить {{a}, {b}}.

Давайте соберем все это вместе:

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) <br/>
{ <br/>
    // основа индукции: <br/>
    IEnumerable<IEnumerable<T>> result = new[] { Enumerable.Empty<T>() }; <br/>
    foreach(var sequence in sequences) <br/>
    { <br/>
        var s = sequence; // нельзя замыкаться на переменную цикла <br/>
        // индукционный переход: используем SelectMany, чтобы построить новое произведение из старого <br/>
        result =  <br/>
            from seq in result <br/>
            from item in s <br/>
            select seq.Concat(new[] {item}); <br/>
    } <br/>
    return result; <br/>
} 

Работает отлично, но при желании можно сделать чуточку красивее. По существу мы здесь используем аккумулятор. Рассмотрим пример проще, скажем, суммирование списка целых чисел. Один из способов сделать это — сказать «Пусть аккумулятор вначале равен нулю. Новый аккумулятор получается из старого путем добавления текущего элемента к старому аккумулятору». Если у нас есть стартовое значение аккумулятора и мы некоторым образом можем получить новое значение из старого и из текущего элемента последовательности, тогда можно использовать полезный метод Aggregate. Он принимает стартовое значение аккумулятора и функцию, которая принимает последнее значение и текущий элемент и возвращает новое значение аккумулятора. На выходе метода — итоговое значение аккумулятора.

В данном случае мы начнем с пустым произведением в качестве аккумулятора, и каждый раз мы будем «добавлять» к нему путем комбинирования текущей последовательности с произведением предыдущих. На каждом шаге алгоритма, аккумулятор равен декартовому произведению уже просмотренных последовательностей.

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) <br/>
{ <br/>
    IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; <br/>
    return sequences.Aggregate( <br/>
        emptyProduct, <br/>
        (accumulator, sequence) =>  <br/>
            from accseq in accumulator  <br/>
            from item in sequence  <br/>
            select accseq.Concat(new[] {item}));                <br/>
}

И напоследок несколько слов для разбирающихся. Помните, результат LINQ-запроса есть запрос, который предоставит результаты по требованию, а не результаты непосредственно. Когда мы строим этот аккумулятор, мы вообще-то не вычисляем декартово произведение. Мы строим большой сложный запрос, который при запуске выдаст декартово произведение. Запрос строится энергично, но выполняться будет лениво.

От переводчика

Эрик обошел в своем посте конкретное название идиомы, которую он использовал, а именно свертки. Впрочем, на эту тему на Хабрахабре уже были посты. Интересующийся может найти отличный перевод «Катаморфизм в F#».

Ту же задачу, гораздо менее многословно, но с тем же алгоритмом, можно решить и на F#. Вместо LINQ в код хорошо впишутся списочные выражения (list comprehensions) — одна из замечательных фич, традиционно свойственных функциональным языкам. Для достижения большей производительности приклеивать элемент к списку стоит с головы, оператором (::). В таком случае для достижения классического вида декартова произведения исходную последовательность перед началом работы придется перевернуть.

В сумме свертка, пайплайны и списочные выражения дадут вот такой красивый код:

let product seqs =
    List.rev seqs
    |> List.fold
        (fun acc cur ->
            [for seq in acc do
                for item in cur do
                    yield item::seq]) [[]]