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.

Your question seems to be about permutations but your linked answer is about combinations. So the snippet gives combinations and thus isn't useful for your problem... right? — Klaycon, May 11 '20 at 18:27
You say you want permutations but your answer seems to not include e.g. `{ 4, 3, 2, 1 }`? Show a simpler example where you can list all of the answer... — NetMage, May 11 '20 at 19:11
What should happen if one of the lists passed in is a different length? — juharr, May 11 '20 at 19:11
I manage to work with the link solution, which is why i posted here. But if you think it's confusing i can remove — AdrianoRR, May 11 '20 at 19:12
@NetMage I'm taking the example to mean they want all combinations where the first item is the first item of one of the lists, and the second is the second item of one of the lists, and so on. — juharr, May 11 '20 at 19:13
@juharr it should set null if it does not find a corresponding item to permutate — AdrianoRR, May 11 '20 at 19:14
If you change the lists to (1,5,9);(2,6,7),(3,7),(4,8,0) then what you want is the cartesian product of those sets and here's a good blog about how to do that https://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/ — juharr, May 11 '20 at 19:31

score 2 · Accepted Answer · answered May 11 '20 at 19:46

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

Amazing, that did the trick! Thank you. I read Eric Lippert's blog about 5 days ago when this problem came up but couldn't do much. — AdrianoRR, May 11 '20 at 20:16

Guru Stron · Answer 2 · 2020-05-11T20:10:35.847

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

edited May 11 '20 at 20:10

answered May 11 '20 at 19:51

Guru Stron

102,774
10
95
132

1

That is a better way to do the pivot. – juharr May 11 '20 at 20:03
@juharr, thank you for improvement (also will need to correct `GroupBy` cause `T` is value tuple `(item, index)`) . – Guru Stron May 11 '20 at 20:08
Yeah, just a `Select(grp => grp.Select(x => x.item))` will work, the `ToList` is not needed. – juharr May 11 '20 at 20:09
@juharr, just selected in `GroupBy` clause =) – Guru Stron May 11 '20 at 20:12

score 0 · Answer 3 · answered May 12 '20 at 15:56

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

Permutation between multiple arrays with null values

3 Answers3