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
– Klaycon, Commented May 11, 2020 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
– NetMage, Commented May 11, 2020 at 19:11
What should happen if one of the lists passed in is a different length? — juharr
– juharr, Commented May 11, 2020 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
– AdrianoRR, Commented May 11, 2020 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
– juharr, Commented May 11, 2020 at 19:13

juharr · Accepted Answer · 2020-05-11 19:46:44Z

2

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

answered May 11, 2020 at 19:46

juharr

32.4k4 gold badges60 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

AdrianoRR Over a year ago

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.

Guru Stron · Accepted Answer · 2020-05-11 20:10:35Z

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, 2020 at 20:10

answered May 11, 2020 at 19:51

Guru Stron

150k11 gold badges186 silver badges232 bronze badges

4 Comments

juharr Over a year ago

That is a better way to do the pivot.

Guru Stron Over a year ago

@juharr, thank you for improvement (also will need to correct GroupBy cause T is value tuple (item, index)) .

juharr Over a year ago

Yeah, just a Select(grp => grp.Select(x => x.item)) will work, the ToList is not needed.

Guru Stron Over a year ago

@juharr, just selected in GroupBy clause =)

NetMage · Accepted Answer · 2020-05-12 15:56:54Z

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

Collectives™ on Stack Overflow

Permutation between multiple arrays with null values

3 Answers 3

1 Comment

4 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related