Permutation between multiple arrays with null values

Question

I'm trying to permute multiple arrays of different sizes with null values. Something like:

IEnumerable<IEnumerable<T>> GetAllPermutations<T>(IEnumerable<IEnumerable<T>> lists)
{
  // if it received a list with 4 elements, it must return a list of list with 4 permutations
}

Example:

var list1 = new List<string>() { "1", "2", "3", "4" };
var list2 = new List<string>() { "5", "6", "7", "8" };
var list3 = new List<string>() { "9", "7", null, "0" };

var fullList = new List<List<string>>() { list1, list2, list3 };

var result = GetAllPermutations(fullList);

Result: 81 permutations (3^4)

{ "1", "2", "3", "4" }
{ "5", "2", "3", "4" }
{ "1", "6", "3", "4" }
{ "1", "2", "7", "4" }
{ "1", "2", "3", "8" }
.
.
.
.
.
{ "1", "9", "null", "0" }
{ "9", "7", null, "0" }

I've tried a lot of stuff but none of it worked out. The best thing i've found was this answer from another question:

var cc = Enumerable
                .Range(1, (1 << simpleList.Count) - 1)
                .Select(index => simpleList.Where((item, idx) => ((1 << idx) & index) != 0).ToList());

But it doesn't work with multiple lists.

EDIT: The example above is a combinatoric answer which worked for me when i was working with another problem. It does generate some permutations but not all and it does not work with multiple lists.

Answer 1

Using an extension method for integral power, you can treat the output as a base b number with n digits, and compute each digit position's value then convert to the characters from the input.

First, the integral power extension method:

public static int Pow(this int x, int pow) {
    int ret = 1;
    while (pow != 0) {
        if ((pow & 1) == 1)
            ret *= x;
        x *= x;
        pow >>= 1;
    }
    return ret;
}

Now, you can convert the input to a list of lists for lookup, then compute the (in the example) 4 digit numbers and map to the input alphabet:

var numbase = fullList.Count;
var digits = fullList[0].Count;
var alpha = fullList.Select(l => l.ToList()).ToList();
var ans = Enumerable.Range(0, numbase.Pow(digits))
                    .Select(n => Enumerable.Range(0, digits).Select(d => alpha[(n / (numbase.Pow(d))) % numbase][d]));

Answer 2

Leveraging Cartesian product by Eric Lippert:

static IEnumerable<IEnumerable<T>> GetAllPermutations<T>(IEnumerable<List<T>> lists)
{
    return lists.SelectMany(l => l.Select((item, index) => (item, index)))
        .GroupBy(c => c.index, c => c.item) // each group will have items allowed on n-th position
        .OrderBy(g => g.Key) // actually not needed in this case, but just to be sure
        .CartesianProduct();
}

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

Answer 3

It looks like you want the Cartesian Product of the Pivot of those sets. So using the following method from Eric Lippert's blog about doing the Cartesian Product of sets

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 this code to do the Pivot

IEnumerable<IEnumerable<T>> Pivot<T>(IEnumerable<IEnumerable<T>> lists)
{
    var pivot = new List<List<T>>();

    foreach(var sub in lists)
    {
        int i = 0;
        foreach(var val in sub)
        {
            if(pivot.Count <= i)
            {
                pivot.Add(new List<T>());
            }
            pivot[i].Add(val);

            i++;
        }
    }

    return pivot;
}

You should get your answer by doing the following.

var list1 = new List<string>() { "1", "2", "3", "4" };
var list2 = new List<string>() { "5", "6", "7", "8" };
var list3 = new List<string>() { "9", "7", null, "0" };

var fullList = new List<List<string>>() { list1, list2, list3 };

var result = CartesianProduct(Pivot(fullList));