Пример создания n-арного декартова произведения

Я обнаружил, что сообщение Эрика Липперта здесь подходит для моей конкретной проблемы.

Проблема в том, что я не могу понять, как я должен использовать его с количеством коллекций 2+.

Имея

var collections = new List<List<MyType>>();
foreach(var item in somequery)
{
    collections.Add(
            new List<MyType> { new MyType { Id = 1} .. n }
        );
}

Как применить linq-запрос декартового продукта к коллекциям variabile ?

Метод расширения таков:

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})                       
        );
 }

Вот пример Эрика для 2 коллекций:

var arr1 = new[] {"a", "b", "c"};
var arr2 = new[] { 3, 2, 4 };
var result = from cpLine in CartesianProduct(
                     from count in arr2 select Enumerable.Range(1, count)) 
             select cpLine.Zip(arr1, (x1, x2) => x2 + x1);

.net c# linq cartesian-product
person Stefan Anghel    schedule 30.11.2012    source источник
comment
возможный дубликат списков перестановок (неизвестный номер)   -  person Rawling    schedule 30.11.2012
comment
Метод расширения @EricLippert гораздо более понятен (по крайней мере, для меня) и лаконичен, чем любое из решений в этих возможных дубликатах.   -  person Stefan Anghel    schedule 30.11.2012

Ответы (3)


arrow_upward
5
arrow_downward

Пример кода уже может делать «n» декартовых произведений (в примере это 3). Ваша проблема в том, что у вас есть List<List<MyType>>, когда вам нужно IEnumerable<IEnumerable<MyType>>

IEnumerable<IEnumerable<MyType>> result = collections
  .Select(list => list.AsEnumerable())
  .CartesianProduct();
person Amy B    schedule 30.11.2012
comment
нет необходимости использовать AsEnumerable(), так как каждый список уже является IEnumerable, см.: stackoverflow.com/a/46327167/1819480 - person TermoTux; 20.09.2017
comment
@Infinum Не совсем ... метод CartesianProduct принимает IEnumerable<IEnumerable<T>> Если вы не вызываете AsEnumerable, у вас есть IEnumerable<List<T>>, который несовместим. - person Amy B; 21.09.2017

arrow_upward
0
arrow_downward

Поскольку List<T> равно IEnumerable<T>, ваша проблема с использованием решения Эрика решается следующим образом:

var collections = new List<List<MyType>>();
var product =  collections.CartesianProduct();
foreach(var collection in product)
{
    // a single collection of MyType items
    foreach(var item in collection)
    {
        // each item of type MyType within a collection
        Console.Write(item);
    }    
}

Конечно, вы можете объединить элементы из каждой коллекции в более сжатой форме, например, в виде одного string:

var product = 
    collections
    .CartesianProduct()
    .Select(xs => xs.Aggregate(new StringBuilder(), (sb, x) => sb.Append(x.ToString()), sb => sb.ToString()));

foreach(var collectionAsString in product)
{
    Console.WriteLine(collectionAsString);
}
person TermoTux    schedule 20.09.2017

arrow_upward
0
arrow_downward

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

Мой код был настроен так, что у меня было 3 массива с данными, которые мне нужно было перемножить вместе, и создание этого большего IEnumerable выходило за рамки моего пути, и я не хотел этого делать.

Поэтому вместо этого я переписал функцию, чтобы она расширялась от IEnumerable<T> вместо IEnumerable<IEnumerable<T>>, поэтому теперь я могу вызывать функцию непосредственно из любого из массивов, которые я хочу умножить, и просто передавать два других массива в качестве параметров. Я подумал, что сделаю репост здесь, если кто-то еще заинтересован в использовании его таким образом:

    public static IEnumerable<IEnumerable<T>> CartesianProduct<T>
    (this IEnumerable<T> firstSequence, params IEnumerable<T>[] sequences)
    {
        IEnumerable<IEnumerable<T>> result = new[] { Enumerable.Empty<T>() };

        foreach (IEnumerable<T> sequence in (new[] { firstSequence }).Concat(sequences))
        {
            result = from resultItem in result 
                     from sequenceItem in sequence 
                     select resultItem.Concat(new[] { sequenceItem });
        }
        return result;
    }

Это будет пример использования этого метода для 3 массивов данных.

        var numbers = new object[] { 1, 2, 3 };
        var letters = new object[] { "a", "b", "c" };
        var colors = new object[] { "red", "blue", "yellow" };

        var result = numbers.CartesianProduct(letters, colors);

Выход

        [1, a, red]
        [1, a, blue]
        [1, a, yellow]
        [1, b, red]
        [1, b, blue]
        [1, b, yellow]
        [1, c, red]
        [1, c, blue]
        [1, c, yellow]
        [2, a, red]
        [2, a, blue]
        [2, a, yellow]
        [2, b, red]
        [2, b, blue]
        [2, b, yellow]
        [2, c, red]
        [2, c, blue]
        [2, c, yellow]
        [3, a, red]
        [3, a, blue]
        [3, a, yellow]
        [3, b, red]
        [3, b, blue]
        [3, b, yellow]
        [3, c, red]
        [3, c, blue]
        [3, c, yellow]
person Blake    schedule 09.07.2021