Cartesian Product of an arbitrary number of objects

Question

I'm looking to get the Cartesian Product of an arbitrary number of objects in c#. My situation is slightly unusual - my inputs are not lists of base types, but objects which have a property that's a list of base types.

My input and output objects are as follows:

public class Input
{
    public string Label;
    public List<int> Ids;
}

public class Result
{
    public string Label;
    public int Id;
}

Some sample input data:

var inputs = new List<Input>
{
    new Input { Label = "List1", Ids = new List<int>{ 1, 2 } },
    new Input { Label = "List2", Ids = new List<int>{ 2, 3 } },
    new Input { Label = "List3", Ids = new List<int>{ 4 } }
};

And my expected output object:

var expectedResult = new List<List<Result>>
{
    new List<Result>
    {
        new Result{Label = "List1", Id = 1},
        new Result{Label = "List2", Id = 2},
        new Result{Label = "List3", Id = 4}
    },
    new List<Result>
    {
        new Result{Label = "List1", Id = 1},
        new Result{Label = "List2", Id = 3},
        new Result{Label = "List3", Id = 4}
    },
    new List<Result>
    {
        new Result{Label = "List1", Id = 2},
        new Result{Label = "List2", Id = 2},
        new Result{Label = "List3", Id = 4}
    },
    new List<Result>
    {
        new Result{Label = "List1", Id = 2},
        new Result{Label = "List2", Id = 3},
        new Result{Label = "List3", Id = 4}
    }
};

If I knew the number of items in 'inputs' in advance I could do this:

var knownInputResult = 
    from id1 in inputs[0].Ids
    from id2 in inputs[1].Ids
    from id3 in inputs[2].Ids
    select
    new List<Result>
    {
        new Result { Id = id1, Label = inputs[0].Label },
        new Result { Id = id2, Label = inputs[1].Label },
        new Result { Id = id3, Label = inputs[2].Label },
    };

I'm struggling to adapt this to an arbitrary number of inputs - is there a possible way to do this?

See also: https://stackoverflow.com/questions/3093622/generating-all-possible-combinations — Emond, Apr 10 '18 at 16:54
Thanks for looking at this Erno. I've looked at various Cartesian product answers already - however they all deal with inputs which are of base types (eg, `List`). I'm looking to use a property in my input lists as the comparison for the Cartesian product which makes it a little trickier. Neither the duplicate link, nor the link in the comment address this part, so would it be possible for you to reopen this please? — John, Apr 10 '18 at 16:58

score 1 · Accepted Answer · answered Apr 10 '18 at 17:54

I consider this duplicate of question linked in comments, but since it was reopened and you struggle to adapt that question to your case, here is how.

First grab function by Eric Lippert from duplicate question as is (how it works is explained there):

public static class Extensions {
    public 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 })
        );
    }
}

Then flatten your input. Basically just attach corresponding label to each id:

var flatten = inputs.Select(c => c.Ids.Select(r => new Result {Label = c.Label, Id = r}));

Then run cartesian product and done:

// your expected result
var result = flatten.CartesianProduct().Select(r => r.ToList()).ToList();

score 0 · Answer 2 · answered Apr 10 '18 at 17:48

I'm not proud of the amount of time I spent messing with this, but it works. It's basically black magic, and I would replace it the first chance you get.

public static List<List<Result>> Permutate(IEnumerable<Input> inputs)
{
    List<List<Result>> results = new List<List<Result>>();

    var size = inputs.Select(inp => factorial_WhileLoop(inp.Ids.Count)).Aggregate((item, carry) => item + carry) - 1;

    for (int i = 0; i < size; i++) results.Add(new List<Result>());

    foreach (var input in inputs)
    {
        for (int j = 0; j < input.Ids.Count; j++)
        {
            for (int i = 0; i < (size / input.Ids.Count); i++)
            {
                var x = new Result() { Label = input.Label, Id = input.Ids[j] };

                results[(input.Ids.Count * i) + j].Add(x);
            }
        }
    }

    return results;
}

public static int factorial_WhileLoop(int number)
{
    var result = 1;
    while (number != 1)
    {
        result = result * number;
        number = number - 1;
    }
    return result;
}

Cartesian Product of an arbitrary number of objects

2 Answers2