CODEWITHSUNDEEP
c#algorithmlinq
Michael0x2a
Michael0x2a

Reputation: 63988

How to "zip" or "rotate" a variable number of lists?

If I have a list containing an arbitrary number of lists, like so:

var myList = new List<List<string>>()
{
    new List<string>() { "a", "b", "c", "d" },
    new List<string>() { "1", "2", "3", "4" },
    new List<string>() { "w", "x", "y", "z" },
    // ...etc...
};

...is there any way to somehow "zip" or "rotate" the lists into something like this?

{ 
    { "a", "1", "w", ... },
    { "b", "2", "x", ... },
    { "c", "3", "y", ... },
    { "d", "4", "z", ... }
}

The obvious solution would be to do something like this:

public static IEnumerable<IEnumerable<T>> Rotate<T>(this IEnumerable<IEnumerable<T>> list)
{
    for (int i = 0; i < list.Min(x => x.Count()); i++)
    {
        yield return list.Select(x => x.ElementAt(i));
    }
}

// snip

var newList = myList.Rotate();

...but I was wondering if there was a cleaner way of doing so, using linq or otherwise?

Upvotes: 16

Views: 1712

Answers (7)

Eric Lippert
Eric Lippert

Reputation: 659974

You can roll your own ZipMany instance which manually iterates each of the enumerations. This will likely perform better on larger sequences than those using GroupBy after projecting each sequence:

public static IEnumerable<TResult> ZipMany<TSource, TResult>(
    IEnumerable<IEnumerable<TSource>> source,
    Func<IEnumerable<TSource>, TResult> selector)
{
   // ToList is necessary to avoid deferred execution
   var enumerators = source.Select(seq => seq.GetEnumerator()).ToList();
   try
   {
     while (true)
     {
       foreach (var e in enumerators)
       {
           bool b = e.MoveNext();
           if (!b) yield break;
       }
       // Again, ToList (or ToArray) is necessary to avoid deferred execution
       yield return selector(enumerators.Select(e => e.Current).ToList());
     }
   }
   finally
   {
       foreach (var e in enumerators) 
         e.Dispose();
   }
}

Upvotes: 18

Amir Liberman
Amir Liberman

Reputation: 41

Take a look at the linqlib project on codeplex, it has a rotate function that does exactly what you need.

Upvotes: 2

JerKimball
JerKimball

Reputation: 16894

Here's an inefficient variant based on Matrix Transposition:

public static class Ext
{
    public static IEnumerable<IEnumerable<T>> Rotate<T>(
        this IEnumerable<IEnumerable<T>> src)
    {
        var matrix = src.Select(subset => subset.ToArray()).ToArray();
        var height = matrix.Length;
        var width = matrix.Max(arr => arr.Length);

        T[][] transpose = Enumerable
            .Range(0, width)
            .Select(_ => new T[height]).ToArray();
        for(int i=0; i<height; i++)
        {        
            for(int j=0; j<width; j++)
            {            
                transpose[j][i] = matrix[i][j];            
            }
        }

        return transpose;
    }
}

Upvotes: 3

Simon Belanger
Simon Belanger

Reputation: 14870

You can do this by using the Select extension taking a Func<T, int, TOut>:

var rotatedList = myList.Select(inner => inner.Select((s, i) => new {s, i}))
                        .SelectMany(a => a)
                        .GroupBy(a => a.i, a => a.s)
                        .Select(a => a.ToList()).ToList();

This will give you another List<List<string>>.

Breakdown

.Select(inner => inner.Select((s, i) => new {s, i}))

For each inner list, we project the list's content to a new anonymous object with two properties: s, the string value, and i the index of that value in the original list.

.SelectMany(a => a)

We flatten the result to a single list

.GroupBy(a => a.i, a => a.s)

We group by the i property of our anonymous object (recall this is the index) and select the s property as our values (the string only).

.Select(a => a.ToList()).ToList();

For each groups, we changed the enumerable to a list and another list for all the groups.

Upvotes: 12

Nate Diamond
Nate Diamond

Reputation: 5575

(from count in Range(myList[0].Count)
select new List<string>(
    from count2 in Range(myList.Count)
    select myList[count2][count])
    ).ToList();

It ain't pretty, but I think it'll work.

Upvotes: 0

user7116
user7116

Reputation: 64068

How about using SelectMany and GroupBy with some indexes?

// 1. Project inner lists to a single list (SelectMany)
// 2. Use "GroupBy" to aggregate the item's based on order in the lists
// 3. Strip away any ordering key in the final answer
var query = myList.SelectMany(
    xl => xl.Select((vv,ii) => new { Idx = ii, Value = vv }))
       .GroupBy(xx => xx.Idx)
       .OrderBy(gg => gg.Key)
       .Select(gg => gg.Select(xx => xx.Value));

From LinqPad:

we groupa da items

Upvotes: 5

nmclean
nmclean

Reputation: 7724

You can condense for loops using Range:

var result = Enumerable.Range(0, myList.Min(l => l.Count))
    .Select(i => myList.Select(l => l[i]).ToList()).ToList();

Upvotes: 1

Related Questions