Вычисление декартового произведения с помощью LINQ
Вот еще одно сообщение, основанное на очередном вопросе со StackOverflow: как вычислить декартово произведение произвольного количества последовательностей с помощью 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 содержится оператор, предназначенный для декартового произведения: с помощью синтаксиса на основе вызова метода (fluent syntax) – это SelectMany, а с помощью «языка запросов» - это запрос с двумя операторами “from”:
var s1 = new[] {a, b};
var s2 = new[] {x, y, z};
var product =
from first in s1
from second in s2
select new[] { first, second };
Конечно, мы можем обобщить декартово произведение более чем на две последовательности. Декартово произведение n последовательностей {S1, S2, ..., Sn} представляет собой последовательность, которая содержит набор всех возможных последовательностей из n элементов, в которой первый элемент берется из последовательности S1, второй – из S2, и т.д.
В этом определении не учитывается примитивный случай. Чему равняется декартово произведение пустых последовательностей? Давайте обозначим результат декартового произведения одной пустой последовательности следующим образом: { { } }. (См. комментарии для обоснования того, почему это хорошая мысль; изначально я думал использовать пустую последовательность { }, но этот способ лучше. Спасибо Apollonius за отличный совет.)
Обратите внимание, что это приводит нас к разумному определению декартового произведения одной последовательности. Декартово произведение последовательности, содержащей в качестве элемента одну последовательность, скажем { {a, b} }, является последовательность всех возможных последовательностей, состоящих из одного элемента, в которых первым (и единственным) элементом является {a, b}. Т.е. декартовым произведением последовательности { {a, b} } является { {a}, {b} }.
С помощью LINQ вы можете очень легко выполнить декартово произведение любого количества последовательностей, но для этого вы должны знать количество последовательностей.
var product =
from first in s1
from second in s2
from third in s3
select new[] {first, second, third};
А что если вы не знаете количество последовательностей в момент компиляции? Т.е. как вы сможете реализовать тело этого метода:
public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> 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 =
from old in oldProduct
from item in sequence
select old.Concat(new[]{item}};
И теперь мы получаем полноценный рекурсивный случай. Если oldProduct представляет собой любое декартово произведение, тогда мы можем вычислить новое объединение этого произведения с другой последовательностью для создания нового декартового произведения.
Просто ради проверки: учитывает ли этот вариант наш базовый случай? Да. Если мы хотим вычислить декартово произведение { { } } с {a, b} тогда мы объединяем { } с {a} и { } с {b} и получаем { {a}, {b} }.
Давайте соберем все это в одном месте:
static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)
{
// базовый случай:
IEnumerable<IEnumerable<T>> result = new[] { Enumerable.Empty<T>() };
foreach(var sequence in sequences)
{
var s = sequence; // не замыкаем на переменную цикла // рекурсивный случай: используем SelectMany для создания нового произведения на основе исходного произведения
result =
from seq in result
from item in s
select seq.Concat(new[] {item});
}
return result;
}
Вариант хороший, но если нужно, мы можем действовать чуточку хитрее. На самом деле мы используем аккумулятор (accumulator). Давайте рассмотрим простой случай, скажем, добавление суммы к списку целых чисел. Одно из решений состоит в следующем: «накопить все значения, начиная с нулевого. Новый аккумулятор вычисляется на основе старого, путем добавления текущего элемента к предыдущему значению». Если мы начинаем с некоторого значения аккумулятора и некоторым способом создаем новое значение аккумулятора по предыдущему значению и текущему значению элемента последовательности, тогда, в этом случае мы можем воспользоваться удобным методом расширения с именем Aggregate. Он принимает начальное значение аккумулятора и функцию, которая принимает последнее значение и текущий элемент и возвращает следующее значение аккумулятора. Результатом выполнения этого метода является окончательное значение аккумулятора.
В таком случае начальным значением аккумулятора будет пустое произведение, и на каждом шаге мы будем «добавлять» к нему сумму текущей последовательности и полученного произведения. На каждом шаге аккумулятор будет содержать декартово произведение всей последовательности пройденной до этого шага.
static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)
{
IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
return sequences.Aggregate(
emptyProduct,
(accumulator, sequence) =>
from accseq in accumulator
from item in sequence
select accseq.Concat(new[] {item}));
}
А теперь тонкий момент. Помните, что результатом LINQ запроса является запрос, который выдает результат по требованию, но не выдает результат запроса сразу же. Когда мы создаем аккумулятор, мы на самом деле не вычисляем декартово произведение. Мы создаем большой и сложный запрос, который при его выполнении возвращает декартово произведение. Сам запрос строится сразу же, но выполняется отложенно.
Разумно?