Разбить список на несколько списков при увеличении последовательности

Ответ 1

Я бы просто пошел на что-то простое:

public static IEnumerable<List<int>> SplitWhenNotIncreasing(List<int> numbers)
{
    for (int i = 1, start = 0; i <= numbers.Count; ++i)
    {
        if (i != numbers.Count && numbers[i] > numbers[i - 1])
            continue;

        yield return numbers.GetRange(start, i - start);
        start = i;
    }
}

Что вы будете использовать так:

List<int> data = new List<int> { 1, 2, 1, 2, 3, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 6 };

foreach (var subset in SplitWhenNotIncreasing(data))
    Console.WriteLine(string.Join(", ", subset));

Если вам действительно нужно работать с IEnumerable<T>, то самый простой способ, который я могу представить, это:

public sealed class IncreasingSubsetFinder<T> where T: IComparable<T>
{
    public static IEnumerable<IEnumerable<T>> Find(IEnumerable<T> numbers)
    {
        return new IncreasingSubsetFinder<T>().find(numbers.GetEnumerator());
    }

    IEnumerable<IEnumerable<T>> find(IEnumerator<T> iter)
    {
        if (!iter.MoveNext())
            yield break;

        while (!done)
            yield return increasingSubset(iter);
    }

    IEnumerable<T> increasingSubset(IEnumerator<T> iter)
    {
        while (!done)
        {
            T prev = iter.Current; 
            yield return prev;

            if ((done = !iter.MoveNext()) || iter.Current.CompareTo(prev) <= 0)
                yield break;
        }
    }

    bool done;
}

Что вы бы назвали так:

List<int> data = new List<int> { 1, 2, 1, 2, 3, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 6 };

foreach (var subset in IncreasingSubsetFinder<int>.Find(data))
    Console.WriteLine(string.Join(", ", subset));

Ответ 2

Это не типичная операция LINQ, так как обычно в таких случаях (когда вы настаиваете на использовании LINQ) я бы предложил использовать Aggregate метод:

var result = data.Aggregate(new List<List<int>>(), (r, n) =>
{
    if (r.Count == 0 || n <= r.Last().Last()) r.Add(new List<int>());
    r.Last().Add(n);
    return r;
});

Ответ 3

Вы можете использовать индекс для получения предыдущего элемента и вычислять id группы из сравнения значений. Затем группу на идентификаторы группы и выведите значения:

List<int> data = new List<int> { 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 6 };

int groupId = 0;
var groups = data.Select
                 ( (item, index)
                   => new
                      { Item = item
                      , Group = index > 0 && item <= data[index - 1] ? ++groupId : groupId
                      }
                 );

List<List<int>> list = groups.GroupBy(g => g.Group)
                             .Select(x => x.Select(y => y.Item).ToList())
                             .ToList();

Ответ 4

Мне действительно нравится решение Мэтью Уотсона. Если, однако, вы не хотите полагаться на List<T>, вот мой простой общий подход, перечисляющий перечислимый один раз максимум и сохраняющий возможность ленивой оценки.

public static IEnumerable<IEnumerable<T>> AscendingSubsets<T>(this IEnumerable<T> superset) where T :IComparable<T>
{     
    var supersetEnumerator = superset.GetEnumerator();

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

    T oldItem = supersetEnumerator.Current;
    List<T> subset = new List<T>() { oldItem };

    while (supersetEnumerator.MoveNext())
    {
        T currentItem = supersetEnumerator.Current;

        if (currentItem.CompareTo(oldItem) > 0)
        {
            subset.Add(currentItem);
        }
        else
        {
            yield return subset;
            subset = new List<T>() { currentItem };
        }

        oldItem = supersetEnumerator.Current;
    }

    yield return subset;
}

Изменить: Упрощено решение, чтобы использовать только один перечислитель.

Ответ 5

Я изменил ваш код и теперь отлично работает:

        List<int> data = new List<int> { 1, 2, 1, 2, 3,3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 6 };
        List<List<int>> resultLists = new List<List<int>>();
        int last = 0;
        int count = 0;

        var res = data.Where((p, i) =>
        {
            if (i > 0)
            {
                if (p > last && p!=last)
                {
                    resultLists[count].Add(p);
                }
                else
                {
                    count++;
                    resultLists.Add(new List<int>());
                    resultLists[count].Add(p);
                }
            }
            else
            {
                resultLists.Add(new List<int>());
                resultLists[count].Add(p);
            }



            last = p;
            return true;
        }).ToList();

Ответ 6

Вы можете сделать это с помощью Linq, используя индекс для вычисления группы:

var result = data.Select((n, i) => new { N = n, G = (i > 0 && n > data[i - 1] ? data[i - 1] + 1 : n) - i })
                 .GroupBy(a => a.G)
                 .Select(g => g.Select(n => n.N).ToArray())
                 .ToArray();

Ответ 7

Для таких вещей я вообще не поклонник решений, которые используют GroupBy или другие методы, которые материализуют результаты. Причина в том, что вы никогда не знаете, как долго будет входная последовательность, а материализация этих подпоследовательностей может быть очень дорогостоящей.

Я предпочитаю передавать результаты по мере их вытягивания. Это позволяет реализовать IEnumerable<T>, что поток приводит к продолжению потока через преобразование этого потока.

Обратите внимание, что это решение не будет работать, если вы выйдете из итерации через подпоследовательность и хотите продолжить следующую последовательность; если это проблема, то одно из решений, которые материализуют подпоследовательности, вероятно, будет лучше.

Однако для одноразовых итераций всей последовательности (что является наиболее типичным вариантом использования) это будет работать очень хорошо.

Сначала создайте некоторые помощники для наших тестовых классов:

private static IEnumerable<T> CreateEnumerable<T>(IEnumerable<T> enumerable)
{
    // Validate parameters.
    if (enumerable == null) throw new ArgumentNullException("enumerable");

    // Cycle through and yield.
    foreach (T t in enumerable)
        yield return t;
}

private static void EnumerateAndPrintResults<T>(IEnumerable<T> data,
    [CallerMemberName] string name = "") where T : IComparable<T>
{
    // Write the name.
    Debug.WriteLine("Case: " + name);

    // Cycle through the chunks.
    foreach (IEnumerable<T> chunk in data.
        ChunkWhenNextSequenceElementIsNotGreater())
    {
        // Print opening brackets.
        Debug.Write("{ ");

        // Is this the first iteration?
        bool firstIteration = true;

        // Print the items.
        foreach (T t in chunk)
        {
            // If not the first iteration, write a comma.
            if (!firstIteration)
            {
                // Write the comma.
                Debug.Write(", ");
            }

            // Write the item.
            Debug.Write(t);

            // Flip the flag.
            firstIteration = false;
        }

        // Write the closing bracket.
        Debug.WriteLine(" }");
    }
}

CreateEnumerable используется для создания потоковой реализации, а EnumerateAndPrintResults выполняет последовательность, вызывает ChunkWhenNextSequenceElementIsNotGreater (это происходит и выполняет работу) и выводит результаты.

Вот реализация. Заметьте, я решил реализовать их как методы расширения на IEnumerable<T>; это первое преимущество, так как оно не требует материализованной последовательности (технически ни одно из других решений не делает, но лучше явно указать его так).

Во-первых, точки входа:

public static IEnumerable<IEnumerable<T>>
    ChunkWhenNextSequenceElementIsNotGreater<T>(
        this IEnumerable<T> source)
    where T : IComparable<T>
{
    // Validate parameters.
    if (source == null) throw new ArgumentNullException("source");

    // Call the overload.
    return source.
        ChunkWhenNextSequenceElementIsNotGreater(
            Comparer<T>.Default.Compare);
}

public static IEnumerable<IEnumerable<T>>
    ChunkWhenNextSequenceElementIsNotGreater<T>(
        this IEnumerable<T> source,
            Comparison<T> comparer)
{
    // Validate parameters.
    if (source == null) throw new ArgumentNullException("source");
    if (comparer == null) throw new ArgumentNullException("comparer");

    // Call the implementation.
    return source.
        ChunkWhenNextSequenceElementIsNotGreaterImplementation(
            comparer);
}

Обратите внимание, что это работает на все, что реализует IComparable<T> или где вы предоставляете Comparison<T>; это позволяет использовать любой тип и любые правила, которые вы хотите выполнить для сравнения.

Здесь реализация:

private static IEnumerable<IEnumerable<T>>
    ChunkWhenNextSequenceElementIsNotGreaterImplementation<T>(
        this IEnumerable<T> source, Comparison<T> comparer)
{
    // Validate parameters.
    Debug.Assert(source != null);
    Debug.Assert(comparer != null);

    // Get the enumerator.
    using (IEnumerator<T> enumerator = source.GetEnumerator())
    {
        // Move to the first element.  If one can't, then get out.
        if (!enumerator.MoveNext()) yield break;

        // While true.
        while (true)
        {
            // The new enumerator.
            var chunkEnumerator = new 
                ChunkWhenNextSequenceElementIsNotGreaterEnumerable<T>(
                    enumerator, comparer);

            // Yield.
            yield return chunkEnumerator;

            // If the last move next returned false, then get out.
            if (!chunkEnumerator.LastMoveNext) yield break;
        }
    }
}

Примечание: для управления перечислением подпоследовательностей используется другой класс ChunkWhenNextSequenceElementIsNotGreaterEnumerable<T>. Этот класс будет перебирать каждый элемент из IEnumerator<T>, который получается из исходного IEnumerable<T>.GetEnumerator(), но сохраняет результаты последнего звоните в IEnumerator<T>.MoveNext().

Этот генератор подпоследовательности сохраняется, а значение последнего вызова MoveNext проверяется, чтобы увидеть, был ли конец последовательности или не был удален. Если он имеет, то он просто ломается, иначе он переходит к следующему фрагменту.

Здесь реализация ChunkWhenNextSequenceElementIsNotGreaterEnumerable<T>:

internal class 
    ChunkWhenNextSequenceElementIsNotGreaterEnumerable<T> : 
        IEnumerable<T>
{
    #region Constructor.

    internal ChunkWhenNextSequenceElementIsNotGreaterEnumerable(
        IEnumerator<T> enumerator, Comparison<T> comparer)
    {
        // Validate parameters.
        if (enumerator == null) 
            throw new ArgumentNullException("enumerator");
        if (comparer == null) 
            throw new ArgumentNullException("comparer");

        // Assign values.
        _enumerator = enumerator;
        _comparer = comparer;
    }

    #endregion

    #region Instance state.

    private readonly IEnumerator<T> _enumerator;

    private readonly Comparison<T> _comparer;

    internal bool LastMoveNext { get; private set; }

    #endregion

    #region IEnumerable implementation.

    public IEnumerator<T> GetEnumerator()
    {
        // The assumption is that a call to MoveNext 
        // that returned true has already
        // occured.  Store as the previous value.
        T previous = _enumerator.Current;

        // Yield it.
        yield return previous;

        // While can move to the next item, and the previous 
        // item is less than or equal to the current item.
        while ((LastMoveNext = _enumerator.MoveNext()) && 
            _comparer(previous, _enumerator.Current) < 0)
        {
            // Yield.
            yield return _enumerator.Current;

            // Store the previous.
            previous = _enumerator.Current;
        }
    }

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

    #endregion
}

Здесь тест для исходного условия в вопросе, а также вывод:

[TestMethod]
public void TestStackOverflowCondition()
{
    var data = new List<int> { 
        1, 2, 1, 2, 3, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 6 
    };
    EnumerateAndPrintResults(data);
}

Вывод:

Case: TestStackOverflowCondition
{ 1, 2 }
{ 1, 2, 3 }
{ 3 }
{ 1, 2, 3, 4 }
{ 1, 2, 3, 4, 5, 6 }

Здесь тот же ввод, но передается как перечислимый:

[TestMethod]
public void TestStackOverflowConditionEnumerable()
{
    var data = new List<int> { 
        1, 2, 1, 2, 3, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 6 
    };
    EnumerateAndPrintResults(CreateEnumerable(data));
}

Вывод:

Case: TestStackOverflowConditionEnumerable
{ 1, 2 }
{ 1, 2, 3 }
{ 3 }
{ 1, 2, 3, 4 }
{ 1, 2, 3, 4, 5, 6 }

Здесь тест с непоследовательными элементами:

[TestMethod]
public void TestNonSequentialElements()
{
    var data = new List<int> { 
        1, 3, 5, 7, 6, 8, 10, 2, 5, 8, 11, 11, 13 
    };
    EnumerateAndPrintResults(data);
}

Вывод:

Case: TestNonSequentialElements
{ 1, 3, 5, 7 }
{ 6, 8, 10 }
{ 2, 5, 8, 11 }
{ 11, 13 }

Наконец, вот тест с символами вместо чисел:

[TestMethod]
public void TestNonSequentialCharacters()
{
    var data = new List<char> { 
        '1', '3', '5', '7', '6', '8', 'a', '2', '5', '8', 'b', 'c', 'a' 
    };
    EnumerateAndPrintResults(data);
}

Вывод:

Case: TestNonSequentialCharacters
{ 1, 3, 5, 7 }
{ 6, 8, a }
{ 2, 5, 8, b, c }
{ a }

Ответ 8

Это мой простой подход к циклу с использованием некоторых выходных данных:

static IEnumerable<IList<int>> Split(IList<int> data) { if (data.Count == 0) yield break; List<int> curr = new List<int>(); curr.Add(data[0]); int last = data[0]; for (int i = 1; i < data.Count; i++) { if (data[i] <= last) { yield return curr; curr = new List<int>(); } curr.Add(data[i]); last = data[i]; } yield return curr; }

Ответ 9

Я использую словарь для получения 5 разных списков, как показано ниже:

static void Main(string[] args)
    {
        List<int> data = new List<int> { 1, 2, 1, 2, 3, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 6 };
        Dictionary<int, List<int>> listDict = new Dictionary<int, List<int>>();

        int listCnt = 1;
        //as initial value get first value from list
        listDict.Add(listCnt, new List<int>());
        listDict[listCnt].Add(data[0]);


        for (int i = 1; i < data.Count; i++)
        {
             if (data[i] > listDict[listCnt].Last())
            {
                listDict[listCnt].Add(data[i]);
            }
             else
            {
                //increase list count and add a new list to dictionary
                listCnt++;
                listDict.Add(listCnt, new List<int>());
                listDict[listCnt].Add(data[i]);
            }
        }

        //to use new lists
        foreach (var dic in listDict)
        {
            Console.WriteLine( $"List {dic.Key} : " + string.Join(",", dic.Value.Select(x => x.ToString()).ToArray()));

        }

    }

Выход:

List 1 : 1,2
List 2 : 1,2,3
List 3 : 3
List 4 : 1,2,3,4
List 5 : 1,2,3,4,5,6