Find all permutations of List>

Question

I've got a situation in which I need to find all permutations of a List of lists of doubles like the following:

List<double> A = new List<double>(){ 1, 2, 3};
List<double> B = new List<double>(){ 10, 20, 30};
List<double> C = new List<double>(){ 100, 200, 300};

needs to give me:

{(1,10,100),(1,10,200),(1,10,300),(1,20,100),(1,20,200),(1,20,300)...}

I can do it for a fixed number of lists, but I want the flexibility (and neatness) of a generalised solution. I've found answers that deal with permutations of a single list, but nothing taking one option from each list, as shown above.

Why do you show code that does not compile? Do you have so little time( but we have )? — Tim Schmelter, Feb 19 '13 at 13:41
See: [Computing a Cartesian Product with LINQ](http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx) from Eric Lippert's blog. — Ani, Feb 19 '13 at 13:45
@TimSchmelter Just trying to give you an idea of what I mean. Also, fixed some typos. — elevenThousand_dB, Feb 19 '13 at 13:47
Do you also want the "1, 2, 3" to appear, or just do it across the lists? — LukeHennerley, Feb 19 '13 at 13:48
@elevenThousand_dB I suspect that all lists will have to be the same length; in this case 3. Otherwise you could end up with `4, null, null`. — LukeHennerley, Feb 19 '13 at 14:29
I wouldn't think they all have to have the same length. You can generate all combinations of items taken from a set of lists of different lengths. Assuming he means that he wants the the n-ary Cartesian Product (as defined at http://en.wikipedia.org/wiki/Cartesian_product) — Matthew Watson, Feb 19 '13 at 16:29

Matthew Watson · Accepted Answer · 2013-02-19T14:03:13.943

Expanding on Ani's comment: I also use Eric Lippert's solution for this kind of thing. (I only really use it for unit testing all possible combinations of small amounts of data.)

using System;
using System.Collections.Generic;
using System.Linq;

namespace Demo
{
    public static class Program
    {
        static void Main(string[] args)
        {
            var a = new List<double> { 1, 2, 3 };
            var b = new List<double> { 10, 20, 30 };
            var c = new List<double> { 100, 200, 300 };

            var lists = new List<List<double>> {a, b, c};

            foreach (var combination in Combine(lists))
            {
                Console.WriteLine(asString(combination));
            }
        }

        static string asString(IEnumerable<double> data)
        {
            return "(" + string.Join(",", data) + ")";
        }

        /// <summary>
        /// Calculates the n-ary Cartesian Product (i.e. all possible combinations) of items taken from any
        /// number of sequences.
        /// </summary>
        /// <typeparam name="T">The type of the items in the sequences.</typeparam>
        /// <param name="sequences">The sequences to combine.</param>
        /// <returns>An enumerator that yields all possible combinations of items.</returns>
        /// <remarks>
        /// This code is taken from http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx
        /// 
        /// If the sequences are ABC and 123, the output will be A1, A2, A3, B1, B2, B3, C1, C2, C3.
        /// </remarks>

        public static IEnumerable<IEnumerable<T>> Combine<T>(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 }));
        }
    }
}

Find all permutations of List>

1 Answers1