Podzielić kolekcję na części „n” za pomocą LINQ?

Czy istnieje dobry sposób na podzielenie kolekcji na nczęści za pomocą LINQ? Oczywiście niekoniecznie równomiernie.

To znaczy, chcę podzielić kolekcję na podkolekcje, z których każda zawiera podzbiór elementów, przy czym ostatnia kolekcja może być poszarpana.

Czysty linq i najprostsze rozwiązanie jest pokazane poniżej.

static class LinqExtensions
{
    public static IEnumerable<IEnumerable<T>> Split<T>(this IEnumerable<T> list, int parts)
    {
        int i = 0;
        var splits = from item in list
                     group item by i++ % parts into part
                     select part.AsEnumerable();
        return splits;
    }
}

EDYCJA: OK, wygląda na to, że źle odczytałem pytanie. Czytam to jako „kawałki o długości n”, a nie „n sztuk”. No! Rozważam usunięcie odpowiedzi ...

(Oryginalna odpowiedź)

Nie wierzę, że istnieje wbudowany sposób partycjonowania, chociaż zamierzam napisać go w moim zestawie dodatków do LINQ to Objects. Marc Gravell ma tutaj implementację, chociaż prawdopodobnie zmodyfikowałbym ją, aby zwracała widok tylko do odczytu:

public static IEnumerable<IEnumerable<T>> Partition<T>
    (this IEnumerable<T> source, int size)
{
    T[] array = null;
    int count = 0;
    foreach (T item in source)
    {
        if (array == null)
        {
            array = new T[size];
        }
        array[count] = item;
        count++;
        if (count == size)
        {
            yield return new ReadOnlyCollection<T>(array);
            array = null;
            count = 0;
        }
    }
    if (array != null)
    {             
        Array.Resize(ref array, count);
        yield return new ReadOnlyCollection<T>(array);
    }
}

static class LinqExtensions
{
    public static IEnumerable<IEnumerable<T>> Split<T>(this IEnumerable<T> list, int parts)
    {
            return list.Select((item, index) => new {index, item})
                       .GroupBy(x => x.index % parts)
                       .Select(x => x.Select(y => y.item));
    }
}

Ok, wrzucę kapelusz na ring. Zalety mojego algorytmu:

1. Żadnych kosztownych operatorów mnożenia, dzielenia lub modułu
2. Wszystkie operacje są O (1) (patrz uwaga poniżej)
3. Działa dla źródła IEnumerable <> (nie jest wymagana właściwość Count)
4. Prosty

Kod:

public static IEnumerable<IEnumerable<T>>
  Section<T>(this IEnumerable<T> source, int length)
{
  if (length <= 0)
    throw new ArgumentOutOfRangeException("length");

  var section = new List<T>(length);

  foreach (var item in source)
  {
    section.Add(item);

    if (section.Count == length)
    {
      yield return section.AsReadOnly();
      section = new List<T>(length);
    }
  }

  if (section.Count > 0)
    yield return section.AsReadOnly();
}

Jak wskazano w komentarzach poniżej, podejście to w rzeczywistości nie odnosi się do pierwotnego pytania, które dotyczyło stałej liczby odcinków o mniej więcej równej długości. To powiedziawszy, nadal możesz zastosować moje podejście do rozwiązania pierwotnego pytania, nazywając je w ten sposób:

myEnum.Section(myEnum.Count() / number_of_sections + 1)

Gdy jest używany w ten sposób, podejście nie jest już O (1), ponieważ operacja Count () to O (N).

To jest to samo, co przyjęta odpowiedź, ale o wiele prostsza reprezentacja:

public static IEnumerable<IEnumerable<T>> Split<T>(this IEnumerable<T> items, 
                                                   int numOfParts)
{
    int i = 0;
    return items.GroupBy(x => i++ % numOfParts);
}

Powyższa metoda dzieli an IEnumerable<T>na liczbę N fragmentów o równych lub zbliżonych rozmiarach.

public static IEnumerable<IEnumerable<T>> Partition<T>(this IEnumerable<T> items, 
                                                       int partitionSize)
{
    int i = 0;
    return items.GroupBy(x => i++ / partitionSize).ToArray();
}

Powyższa metoda dzieli plik IEnumerable<T> na kawałki o pożądanym ustalonym rozmiarze, przy czym całkowita liczba fragmentów jest nieistotna - nie o to chodzi w pytaniu.

Problem z Split metodą, poza tym, że jest wolniejsza, polega na tym, że szyfruje ona dane wyjściowe w tym sensie, że grupowanie zostanie wykonane na podstawie i-tej wielokrotności N dla każdej pozycji, lub innymi słowy, nie dostaniesz fragmentów w pierwotnej kolejności.

Prawie każda odpowiedź tutaj albo nie zachowuje porządku, albo dotyczy partycjonowania, a nie dzielenia, albo jest po prostu błędna. Spróbuj tego, co jest szybsze, zachowuje porządek, ale jest trochę bardziej szczegółowe:

public static IEnumerable<IEnumerable<T>> Split<T>(this ICollection<T> items, 
                                                   int numberOfChunks)
{
    if (numberOfChunks <= 0 || numberOfChunks > items.Count)
        throw new ArgumentOutOfRangeException("numberOfChunks");

    int sizePerPacket = items.Count / numberOfChunks;
    int extra = items.Count % numberOfChunks;

    for (int i = 0; i < numberOfChunks - extra; i++)
        yield return items.Skip(i * sizePerPacket).Take(sizePerPacket);

    int alreadyReturnedCount = (numberOfChunks - extra) * sizePerPacket;
    int toReturnCount = extra == 0 ? 0 : (items.Count - numberOfChunks) / extra + 1;
    for (int i = 0; i < extra; i++)
        yield return items.Skip(alreadyReturnedCount + i * toReturnCount).Take(toReturnCount);
}

Równoważna metoda dla Partitionoperacji tutaj

Dość często korzystałem z funkcji Partition, którą zamieściłem wcześniej. Jedyną złą rzeczą było to, że nie było w pełni przesyłania strumieniowego. Nie stanowi to problemu, jeśli pracujesz z kilkoma elementami w sekwencji. Potrzebowałem nowego rozwiązania, kiedy zacząłem pracować z ponad 100 000 elementami w mojej sekwencji.

Poniższe rozwiązanie jest dużo bardziej złożone (i zawiera więcej kodu!), Ale jest bardzo wydajne.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace LuvDaSun.Linq
{
    public static class EnumerableExtensions
    {
        public static IEnumerable<IEnumerable<T>> Partition<T>(this IEnumerable<T> enumerable, int partitionSize)
        {
            /*
            return enumerable
                .Select((item, index) => new { Item = item, Index = index, })
                .GroupBy(item => item.Index / partitionSize)
                .Select(group => group.Select(item => item.Item)                )
                ;
            */

            return new PartitioningEnumerable<T>(enumerable, partitionSize);
        }

    }


    class PartitioningEnumerable<T> : IEnumerable<IEnumerable<T>>
    {
        IEnumerable<T> _enumerable;
        int _partitionSize;
        public PartitioningEnumerable(IEnumerable<T> enumerable, int partitionSize)
        {
            _enumerable = enumerable;
            _partitionSize = partitionSize;
        }

        public IEnumerator<IEnumerable<T>> GetEnumerator()
        {
            return new PartitioningEnumerator<T>(_enumerable.GetEnumerator(), _partitionSize);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }


    class PartitioningEnumerator<T> : IEnumerator<IEnumerable<T>>
    {
        IEnumerator<T> _enumerator;
        int _partitionSize;
        public PartitioningEnumerator(IEnumerator<T> enumerator, int partitionSize)
        {
            _enumerator = enumerator;
            _partitionSize = partitionSize;
        }

        public void Dispose()
        {
            _enumerator.Dispose();
        }

        IEnumerable<T> _current;
        public IEnumerable<T> Current
        {
            get { return _current; }
        }
        object IEnumerator.Current
        {
            get { return _current; }
        }

        public void Reset()
        {
            _current = null;
            _enumerator.Reset();
        }

        public bool MoveNext()
        {
            bool result;

            if (_enumerator.MoveNext())
            {
                _current = new PartitionEnumerable<T>(_enumerator, _partitionSize);
                result = true;
            }
            else
            {
                _current = null;
                result = false;
            }

            return result;
        }

    }



    class PartitionEnumerable<T> : IEnumerable<T>
    {
        IEnumerator<T> _enumerator;
        int _partitionSize;
        public PartitionEnumerable(IEnumerator<T> enumerator, int partitionSize)
        {
            _enumerator = enumerator;
            _partitionSize = partitionSize;
        }

        public IEnumerator<T> GetEnumerator()
        {
            return new PartitionEnumerator<T>(_enumerator, _partitionSize);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }


    class PartitionEnumerator<T> : IEnumerator<T>
    {
        IEnumerator<T> _enumerator;
        int _partitionSize;
        int _count;
        public PartitionEnumerator(IEnumerator<T> enumerator, int partitionSize)
        {
            _enumerator = enumerator;
            _partitionSize = partitionSize;
        }

        public void Dispose()
        {
        }

        public T Current
        {
            get { return _enumerator.Current; }
        }
        object IEnumerator.Current
        {
            get { return _enumerator.Current; }
        }
        public void Reset()
        {
            if (_count > 0) throw new InvalidOperationException();
        }

        public bool MoveNext()
        {
            bool result;

            if (_count < _partitionSize)
            {
                if (_count > 0)
                {
                    result = _enumerator.MoveNext();
                }
                else
                {
                    result = true;
                }
                _count++;
            }
            else
            {
                result = false;
            }

            return result;
        }

    }
}

Cieszyć się!

Ciekawy wątek. Aby uzyskać wersję strumieniową Split / Partition, można użyć modułów wyliczających i uzyskać sekwencje z modułu wyliczającego przy użyciu metod rozszerzających. Konwersja kodu imperatywnego na kod funkcjonalny przy użyciu wydajności jest rzeczywiście bardzo potężną techniką.

Najpierw rozszerzenie modułu wyliczającego, które zamienia liczbę elementów w leniwą sekwencję:

public static IEnumerable<T> TakeFromCurrent<T>(this IEnumerator<T> enumerator, int count)
{
    while (count > 0)
    {
        yield return enumerator.Current;
        if (--count > 0 && !enumerator.MoveNext()) yield break;
    }
}

A potem wyliczalne rozszerzenie, które dzieli sekwencję:

public static IEnumerable<IEnumerable<T>> Partition<T>(this IEnumerable<T> seq, int partitionSize)
{
    var enumerator = seq.GetEnumerator();

    while (enumerator.MoveNext())
    {
        yield return enumerator.TakeFromCurrent(partitionSize);
    }
}

Efektem końcowym jest wysoce wydajna, strumieniowa i leniwa implementacja, która opiera się na bardzo prostym kodzie.

Cieszyć się!

Używam tego:

public static IEnumerable<IEnumerable<T>> Partition<T>(this IEnumerable<T> instance, int partitionSize)
{
    return instance
        .Select((value, index) => new { Index = index, Value = value })
        .GroupBy(i => i.Index / partitionSize)
        .Select(i => i.Select(i2 => i2.Value));
}

Jest to wydajne pod względem pamięci i opóźnia wykonanie tak bardzo, jak to możliwe (na partię) i działa w czasie liniowym O (n)

    public static IEnumerable<IEnumerable<T>> InBatchesOf<T>(this IEnumerable<T> items, int batchSize)
    {
        List<T> batch = new List<T>(batchSize);
        foreach (var item in items)
        {
            batch.Add(item);

            if (batch.Count >= batchSize)
            {
                yield return batch;
                batch = new List<T>();
            }
        }

        if (batch.Count != 0)
        {
            //can't be batch size or would've yielded above
            batch.TrimExcess();
            yield return batch;
        }
    }

Istnieje wiele świetnych odpowiedzi na to pytanie (i jego kuzynów). Sam tego potrzebowałem i stworzyłem rozwiązanie zaprojektowane tak, aby było wydajne i odporne na błędy w scenariuszu, w którym zbiór źródłowy może być traktowany jako lista. Nie używa żadnej leniwej iteracji, więc może nie być odpowiedni dla kolekcji o nieznanym rozmiarze, które mogą obciążać pamięć.

static public IList<T[]> GetChunks<T>(this IEnumerable<T> source, int batchsize)
{
    IList<T[]> result = null;
    if (source != null && batchsize > 0)
    {
        var list = source as List<T> ?? source.ToList();
        if (list.Count > 0)
        {
            result = new List<T[]>();
            for (var index = 0; index < list.Count; index += batchsize)
            {
                var rangesize = Math.Min(batchsize, list.Count - index);
                result.Add(list.GetRange(index, rangesize).ToArray());
            }
        }
    }
    return result ?? Enumerable.Empty<T[]>().ToList();
}

static public void TestGetChunks()
{
    var ids = Enumerable.Range(1, 163).Select(i => i.ToString());
    foreach (var chunk in ids.GetChunks(20))
    {
        Console.WriteLine("[{0}]", String.Join(",", chunk));
    }
}

Widziałem kilka odpowiedzi w tej rodzinie pytań, które używają GetRange i Math.Min. Uważam jednak, że ogólnie jest to bardziej kompletne rozwiązanie pod względem sprawdzania błędów i wydajności.

   protected List<List<int>> MySplit(int MaxNumber, int Divider)
        {
            List<List<int>> lst = new List<List<int>>();
            int ListCount = 0;
            int d = MaxNumber / Divider;
            lst.Add(new List<int>());
            for (int i = 1; i <= MaxNumber; i++)
            {
                lst[ListCount].Add(i);
                if (i != 0 && i % d == 0)
                {
                    ListCount++;
                    d += MaxNumber / Divider;
                    lst.Add(new List<int>());
                }
            }
            return lst;
        }

Świetne odpowiedzi, dla mojego scenariusza przetestowałem zaakceptowaną odpowiedź i wygląda na to, że nie utrzymuje porządku. Jest też świetna odpowiedź Nawfala, która utrzymuje porządek. Ale w moim scenariuszu chciałem podzielić resztę w znormalizowany sposób, wszystkie odpowiedzi, które widziałem, rozprzestrzeniły się na resztę lub na początku lub na końcu.

Moja odpowiedź obejmuje również dalsze rozprzestrzenianie się w bardziej znormalizowany sposób.

 static class Program
{          
    static void Main(string[] args)
    {
        var input = new List<String>();
        for (int k = 0; k < 18; ++k)
        {
            input.Add(k.ToString());
        }
        var result = splitListIntoSmallerLists(input, 15);            
        int i = 0;
        foreach(var resul in result){
            Console.WriteLine("------Segment:" + i.ToString() + "--------");
            foreach(var res in resul){
                Console.WriteLine(res);
            }
            i++;
        }
        Console.ReadLine();
    }

    private static List<List<T>> splitListIntoSmallerLists<T>(List<T> i_bigList,int i_numberOfSmallerLists)
    {
        if (i_numberOfSmallerLists <= 0)
            throw new ArgumentOutOfRangeException("Illegal value of numberOfSmallLists");

        int normalizedSpreadRemainderCounter = 0;
        int normalizedSpreadNumber = 0;
        //e.g 7 /5 > 0 ==> output size is 5 , 2 /5 < 0 ==> output is 2          
        int minimumNumberOfPartsInEachSmallerList = i_bigList.Count / i_numberOfSmallerLists;                        
        int remainder = i_bigList.Count % i_numberOfSmallerLists;
        int outputSize = minimumNumberOfPartsInEachSmallerList > 0 ? i_numberOfSmallerLists : remainder;
        //In case remainder > 0 we want to spread the remainder equally between the others         
        if (remainder > 0)
        {
            if (minimumNumberOfPartsInEachSmallerList > 0)
            {
                normalizedSpreadNumber = (int)Math.Floor((double)i_numberOfSmallerLists / remainder);    
            }
            else
            {
                normalizedSpreadNumber = 1;
            }   
        }
        List<List<T>> retVal = new List<List<T>>(outputSize);
        int inputIndex = 0;            
        for (int i = 0; i < outputSize; ++i)
        {
            retVal.Add(new List<T>());
            if (minimumNumberOfPartsInEachSmallerList > 0)
            {
                retVal[i].AddRange(i_bigList.GetRange(inputIndex, minimumNumberOfPartsInEachSmallerList));
                inputIndex += minimumNumberOfPartsInEachSmallerList;
            }
            //If we have remainder take one from it, if our counter is equal to normalizedSpreadNumber.
            if (remainder > 0)
            {
                if (normalizedSpreadRemainderCounter == normalizedSpreadNumber-1)
                {
                    retVal[i].Add(i_bigList[inputIndex]);
                    remainder--;
                    inputIndex++;
                    normalizedSpreadRemainderCounter=0;
                }
                else
                {
                    normalizedSpreadRemainderCounter++;
                }
            }
        }
        return retVal;
    }      

}

Jeśli kolejność w tych częściach nie jest zbyt ważna, możesz spróbować tego:

int[] array = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int n = 3;

var result =
   array.Select((value, index) => new { Value = value, Index = index }).GroupBy(i => i.Index % n, i => i.Value);

// or
var result2 =
   from i in array.Select((value, index) => new { Value = value, Index = index })
   group i.Value by i.Index % n into g
   select g;

Jednak z jakiegoś powodu nie można ich rzutować na IEnumerable <IEnumerable <int>> ...

To jest mój kod, ładny i krótki.

 <Extension()> Public Function Chunk(Of T)(ByVal this As IList(Of T), ByVal size As Integer) As List(Of List(Of T))
     Dim result As New List(Of List(Of T))
     For i = 0 To CInt(Math.Ceiling(this.Count / size)) - 1
         result.Add(New List(Of T)(this.GetRange(i * size, Math.Min(size, this.Count - (i * size)))))
     Next
     Return result
 End Function

To mój sposób, wyliczając przedmioty i dzieląc wiersz po kolumnach

  int repat_count=4;

  arrItems.ForEach((x, i) => {
    if (i % repat_count == 0) 
        row = tbo.NewElement(el_tr, cls_min_height);
    var td = row.NewElement(el_td);
    td.innerHTML = x.Name;
  });

Szukałem podziału takiego jak ten ze stringiem, więc cała Lista jest podzielona według jakiejś zasady, nie tylko pierwsza część, to moje rozwiązanie

List<int> sequence = new List<int>();
for (int i = 0; i < 2000; i++)
{
     sequence.Add(i);
}
int splitIndex = 900;
List<List<int>> splitted = new List<List<int>>();
while (sequence.Count != 0)
{
    splitted.Add(sequence.Take(splitIndex).ToList() );
    sequence.RemoveRange(0, Math.Min(splitIndex, sequence.Count));
}

Oto mała zmiana liczby przedmiotów zamiast liczby części:

public static class MiscExctensions
{
    public static IEnumerable<IEnumerable<T>> Split<T>(this IEnumerable<T> list, int nbItems)
    {
        return (
            list
            .Select((o, n) => new { o, n })
            .GroupBy(g => (int)(g.n / nbItems))
            .Select(g => g.Select(x => x.o))
        );
    }
}

int[] items = new int[] { 0,1,2,3,4,5,6,7,8,9, 10 };

int itemIndex = 0;
int groupSize = 2;
int nextGroup = groupSize;

var seqItems = from aItem in items
               group aItem by 
                            (itemIndex++ < nextGroup) 
                            ? 
                            nextGroup / groupSize
                            :
                            (nextGroup += groupSize) / groupSize
                            into itemGroup
               select itemGroup.AsEnumerable();

Właśnie natknąłem się na ten wątek, a większość rozwiązań tutaj polega na dodawaniu elementów do kolekcji, skutecznie materializując każdą stronę przed jej zwróceniem. Jest to złe z dwóch powodów - po pierwsze, jeśli twoje strony są duże, istnieje narzut pamięci na wypełnienie strony, po drugie istnieją iteratory, które unieważniają poprzednie rekordy po przejściu do następnego (na przykład, jeśli zawiniesz DataReader w metodzie wyliczającej) .

To rozwiązanie wykorzystuje dwie zagnieżdżone metody modułu wyliczającego, aby uniknąć konieczności buforowania elementów w tymczasowych kolekcjach. Ponieważ iteratory zewnętrzne i wewnętrzne przechodzą przez ten sam wyliczalny, koniecznie współużytkują ten sam moduł wyliczający, dlatego ważne jest, aby nie przesuwać zewnętrznego, dopóki nie zakończysz przetwarzania bieżącej strony. To powiedziawszy, jeśli zdecydujesz się nie iterować przez całą bieżącą stronę, po przejściu do następnej strony to rozwiązanie automatycznie iteruje w przód do granicy strony.

using System.Collections.Generic;

public static class EnumerableExtensions
{
    /// <summary>
    /// Partitions an enumerable into individual pages of a specified size, still scanning the source enumerable just once
    /// </summary>
    /// <typeparam name="T">The element type</typeparam>
    /// <param name="enumerable">The source enumerable</param>
    /// <param name="pageSize">The number of elements to return in each page</param>
    /// <returns></returns>
    public static IEnumerable<IEnumerable<T>> Partition<T>(this IEnumerable<T> enumerable, int pageSize)
    {
        var enumerator = enumerable.GetEnumerator();

        while (enumerator.MoveNext())
        {
            var indexWithinPage = new IntByRef { Value = 0 };

            yield return SubPartition(enumerator, pageSize, indexWithinPage);

            // Continue iterating through any remaining items in the page, to align with the start of the next page
            for (; indexWithinPage.Value < pageSize; indexWithinPage.Value++)
            {
                if (!enumerator.MoveNext())
                {
                    yield break;
                }
            }
        }
    }

    private static IEnumerable<T> SubPartition<T>(IEnumerator<T> enumerator, int pageSize, IntByRef index)
    {
        for (; index.Value < pageSize; index.Value++)
        {
            yield return enumerator.Current;

            if (!enumerator.MoveNext())
            {
                yield break;
            }
        }
    }

    private class IntByRef
    {
        public int Value { get; set; }
    }
}