How to get all possible combinations from an array?

Question

I have a Type array and I want to generate all possible combinations for the types. i.e: (assuming only int, bool, and string)

int / bool / string / int, bool / int, string / int, bool, string / int, string, bool / etc.

I saw Eric Lippert's answer here: Generating all Possible Combinations and am using his method but I'm having a hard time modifying it to work with a Type array instead of string / int. The parts that trip me are the "Enumerable.Range()" and the funtion lamba in the last part.

This is what I've tried but isn't compiling because x is an int and not a type.

return from cpLine in CartesianProduct(
       from type in types select Enumerable.Range(1, types.Length))
       select cpLine.Zip(types, (x1, x2) => new Tuple<Type, Type>(x1, x2));

@ErikPhilips While the linked question helps to solve this problem but It seems the question is not a duplicate because the linked question asked to calculate Cartesian Product of 2 array, but this question asked to calculate all possible permutations with repetition that can be constructed from an array with n element. And the result will have (n+n^2+n^3+...+n^n) elements. — Reza Aghaei, Dec 31 '15 at 16:09

score 4 · Accepted Answer · edited May 23 '17 at 10:28

You can use CartesianProduct this way:

var types = new List<Type>() { typeof(int), typeof(bool), typeof(string) };
var result = Enumerable.Range(1, types.Count())
                       .Select(x => types.AsEnumerable()).CartesianProduct().ToList();

I suppose you have CartesianProduct extension method created by Eric Lippert:

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

And here is the output:

01: Int32, Int32, Int32
02: Int32, Int32, Boolean
03: Int32, Int32, String
04: Int32, Boolean, Int32
05: Int32, Boolean, Boolean
06: Int32, Boolean, String
07: Int32, String, Int32
08: Int32, String, Boolean
09: Int32, String, String
10: Boolean, Int32, Int32
11: Boolean, Int32, Boolean
12: Boolean, Int32, String
13: Boolean, Boolean, Int32
14: Boolean, Boolean, Boolean
15: Boolean, Boolean, String
16: Boolean, String, Int32
17: Boolean, String, Boolean
18: Boolean, String, String
19: String, Int32, Int32
20: String, Int32, Boolean
21: String, Int32, String
22: String, Boolean, Int32
23: String, Boolean, Boolean
24: String, Boolean, String
25: String, String, Int32
26: String, String, Boolean
27: String, String, String

EDIT

To get all possible output having all possible count of items from an IEnumerable<T> you can add this extension method:

public static IEnumerable<IEnumerable<T>> GetAllPossibleCombinations<T>(this IEnumerable<T> source)
{
    var result = new List<IEnumerable<T>>().AsEnumerable();
    for (int i = 1; i <= source.Count(); i++)
    {
        var intermediateResult = Enumerable.Range(1, i)
                .Select(x => source.AsEnumerable()).CartesianProduct();
        result = result.Union(intermediateResult);
    }
    return result;
}

And then use it this way:

var types = new List<Type>() { typeof(int), typeof(bool), typeof(string) };
var result = types.GetAllPossibleCombinations();

And here is the output:

01: Int32
02: Boolean
03: String
04: Int32, Int32
05: Int32, Boolean
06: Int32, String
07: Boolean, Int32
08: Boolean, Boolean
09: Boolean, String
10: String, Int32
11: String, Boolean
12: String, String
13: Int32, Int32, Int32
14: Int32, Int32, Boolean
15: Int32, Int32, String
16: Int32, Boolean, Int32
17: Int32, Boolean, Boolean
18: Int32, Boolean, String
19: Int32, String, Int32
20: Int32, String, Boolean
21: Int32, String, String
22: Boolean, Int32, Int32
23: Boolean, Int32, Boolean
24: Boolean, Int32, String
25: Boolean, Boolean, Int32
26: Boolean, Boolean, Boolean
27: Boolean, Boolean, String
28: Boolean, String, Int32
29: Boolean, String, Boolean
30: Boolean, String, String
31: String, Int32, Int32
32: String, Int32, Boolean
33: String, Int32, String
34: String, Boolean, Int32
35: String, Boolean, Boolean
36: String, Boolean, String
37: String, String, Int32
38: String, String, Boolean
39: String, String, String

Thanks so much! The way you used it seems different from Eric's way. I'll have to study harder to understand how it works exactly. Thanks. — , Dec 31 '15 at 05:25
You are welcome, The difference is here: in Eric's example he used 2 array (based on the asked question) but here I made an `IEnumerable>` dynamically. — Reza Aghaei, Dec 31 '15 at 05:31
Oh actually I noticed the output doesn't generate single and double combinations. How can I do this? — , Dec 31 '15 at 09:21

How to get all possible combinations from an array?

1 Answers1

EDIT