title: Using LINQ to iterate combinations
body: <blockquote>
    <p><strong>Possible Duplicate:</strong><br>
    <a href="https://stackoverflow.com/questions/3093622/generating-all-possible-combinations">Generating all Possible Combinations</a><br>
    <a href="https://stackoverflow.com/questions/4073713/is-there-a-good-linq-way-to-do-a-cartesian-product">Is there a good LINQ way to do a cartesian product?</a><br>
    <a href="https://stackoverflow.com/questions/7980505/how-to-generate-combination-of-n-elements-with-limited-supply-of-2-each-without">How to generate combination of N elements with limited supply of 2 each without explicit nested loops</a>  </p>
  </blockquote>
  
  
  
  <p>I have a list of lists, and I want to iterate all the possible combinations where I choose one element from each inner list. This is pretty straightforward if I know at compile-time how many lists there are, but how can I do it when I <em>don't</em> know in advance how many lists there will be?</p>
  
  <p>If I have three lists (and if I know, at compile-time, that there will be exactly three lists), and I want all the combinations of choosing a single element from each of the three lists, I can do that easily with a LINQ query:</p>
  
  <pre><code>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}
  </code></pre>
  
  <p>But how can I do the same thing when I don't know at compile-time how many lists there will be?</p>
  
  <pre><code>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.
  </code></pre>
  
  <p>It seems like this should actually be doable in LINQ -- SelectMany already does the equivalent of two nested foreach loops, so all I need to do is do a bunch of SelectMany calls and then combine all the results with another SelectMany. Or something. But when it starts getting meta like that, my brain gets all tied in knots. I can't get a handle on how to put the pieces together. I can't even figure out what the generic type arguments to the outer SelectMany call would be.</p>
  
  <p>How can I iterate those lists of lists, and return all the combinations, without knowing at compile-time how many lists there will be?</p>
  
  <p>(Note: everywhere I used arrays above, I'd be fine with using <code>IEnumerable&lt;T&gt;</code> instead. Arrays are easier to write in sample code, but I'm expecting that the output is more likely to be in the form <code>IEnumerable&lt;IEnumerable&lt;int&gt;&gt;</code> rather than the <code>int[][]</code> I show in my sample output above.)</p>