Выкарыстанне LINQ для перабору камбінацый

Possible Duplicate:
Generating all Possible Combinations
Is there a good LINQ way to do a cartesian product?
How to generate combination of N elements with limited supply of 2 each without explicit nested loops

У мяне ёсць спіс спісаў, і я хачу, каб перабіраць усе магчымыя камбінацыі, дзе я выбраць адзін элемент з кожнага ўнутранага спісу. Гэта даволі проста, калі я ведаю, што ў час кампіляцыі, колькі спісаў ёсць, але як я магу гэта зрабіць, калі я не загадзя ведаць, колькі спісаў будзе?

Калі ў мяне ёсць тры спісу (і, калі я ведаю, падчас кампіляцыі, што будзе роўна тры спісу), і я хачу, каб усе камбінацыі выбару аднаго элемента з кожных з трох спісаў, я магу зрабіць гэта лёгка з LINQ запыт:

var list1 = new[] { 1, 2 };
var list2 = new[] { 3, 4 };
var list3 = new[] { 5, 6 };
var combinations = from item1 in list1
                   from item2 in list2
                   from item3 in list3
                   select new[] { item1, item2, item3 };
// Results:
// {1, 3, 5}
// {1, 3, 6}
// {1, 4, 5}
// {1, 4, 6}
// {2, 3, 5}
// {2, 3, 6}
// {2, 4, 5}
// {2, 4, 6}

Але як я магу зрабіць тое ж самае, калі я не ведаю, падчас кампіляцыі, колькі спісаў будзе?

var lists = new[] {
    new[] { 1, 2 },
    new[] { 3, 4 },
    new[] { 5, 6 } };
var combinations = ???;

// This particular example happens to be the same inputs as above, so it
// has the same expected outputs. But there could be two lists instead,
// or four, so the three hard-coded "from" clauses won't work.

Падобна на тое, што гэта павінна быць на самой справе выканальна ў LINQ - SelectMany ўжо робіць эквівалент двух ўкладзеных цыклаў па кожнаму элементу, так што ўсё, што мне трэба зрабіць, гэта зрабіць кучу SelectMany званкоў, а затым аб'яднаць усе вынікі з іншым SelectMany. Ці нешта. Але калі ён пачынае атрымліваць мета так, мой мозг атрымлівае ўсё завязана ў вузлах. Я не магу атрымаць ручку, як пакласці кавалачкі разам. Я нават не магу зразумець, што аргументы радавога тыпу да знешняга SelectMany выкліку будуць.

Як я магу перабіраць гэтыя спісы спісаў, і вярнуць усё камбінацыі, не ведаючы, падчас кампіляцыі, колькі спісаў там будзе?

(Note: everywhere I used arrays above, I'd be fine with using IEnumerable instead. Arrays are easier to write in sample code, but I'm expecting that the output is more likely to be in the form IEnumerable> rather than the int[][] I show in my sample output above.)

5
Гэта не з'яўляецца дублікатам якога-небудзь з тых, <я> пытанні - абодва пытання просяць аб фіксаваным колькасці спісаў - але абодва пытання сапраўды на самай справе ўтрымліваюць адказ (тое ж самае адказ чалавека ў абедзвюх выпадках!) для выпадку пераменнага колькасці-спісаў.
дададзена аўтар Joe White, крыніца
@Steven, пытанне, які вы звязаны навей, чым у мяне, так што калі што-небудзь, гэта дублікат гэтага.
дададзена аўтар Joe White, крыніца
і вось ваш адказаць
дададзена аўтар Ufuk Hacıoğulları, крыніца

1 адказы

Вы не можаце выкарыстоўваць SelectMany аб'яднаць SelectMany выклікаў; Вы карыстаецеся запаўняльнік. Код ласкава Эрык Липперт (адказваючы на ​​пытанне, што гэта значна больш канкрэтна, чым гэта адзін, але дае агульны адказ, які адпавядае гэтаму пытанню, а):

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

Як і ўсе адказы Эрыка, ён уключае ў сябе падрабязнага абмеркавання , што выкладвае дакладна як і чаму гэта працуе, з пункту гледжання эквівалентнага кода, ня LINQ.

2
дададзена