将列表拆分为多个列表,其中序列递增
我有一个int列表,我希望在找到较低或相同的数字后拆分原始列表后创建多个List。 数字不按排序顺序排列。
List data = new List { 1, 2, 1, 2, 3, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 6 };
我希望结果如下:
{ 1, 2 } { 1, 2, 3 } { 3 } { 1, 2, 3, 4 } { 1, 2, 3, 4, 5, 6 }
目前,我正在使用以下linq来做到这一点,但没有帮助我:
List data = new List { 1, 2, 1, 2, 3, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 6 }; List<List> resultLists = new List<List>(); var res = data.Where((p, i) => { int count = 0; resultLists.Add(new List()); if (p = data.Count ? i - 1 : i + 1]) { resultLists[count].Add(p); } else { count++; resultLists.Add(new List()); } return true; }).ToList();
我只想做一些简单的事情:
public static IEnumerable> SplitWhenNotIncreasing(List 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 data = new List { 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
,那么我能想到的最简单的方法是这样的:
public sealed class IncreasingSubsetFinder where T: IComparable { public static IEnumerable> Find(IEnumerable numbers) { return new IncreasingSubsetFinder ().find(numbers.GetEnumerator()); } IEnumerable> find(IEnumerator iter) { if (!iter.MoveNext()) yield break; while (!done) yield return increasingSubset(iter); } IEnumerable increasingSubset(IEnumerator iter) { while (!done) { T prev = iter.Current; yield return prev; if ((done = !iter.MoveNext()) || iter.Current.CompareTo(prev) <= 0) yield break; } } bool done; }
您可以这样称呼:
List data = new List { 1, 2, 1, 2, 3, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 6 }; foreach (var subset in IncreasingSubsetFinder .Find(data)) Console.WriteLine(string.Join(", ", subset));
这不是典型的LINQ操作,所以像往常一样在这种情况下(当一个人坚持使用LINQ时)我建议使用Aggregate
方法:
var result = data.Aggregate(new List>(), (r, n) => { if (r.Count == 0 || n <= r.Last().Last()) r.Add(new List()); r.Last().Add(n); return r; });
您可以使用索引获取上一个项目,并在比较值时计算组ID。 然后对组ID进行分组并获取值:
List data = new List { 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 = groups.GroupBy(g => g.Group) .Select(x => x.Select(y => y.Item).ToList()) .ToList();
我非常喜欢Matthew Watson的解决方案 。 但是,如果您不想依赖List
,这是我的简单通用方法,最多枚举一次枚举,并仍保留延迟评估的function。
public static IEnumerable> AscendingSubsets(this IEnumerable superset) where T :IComparable { var supersetEnumerator = superset.GetEnumerator(); if (!supersetEnumerator.MoveNext()) { yield break; } T oldItem = supersetEnumerator.Current; List subset = new List () { oldItem }; while (supersetEnumerator.MoveNext()) { T currentItem = supersetEnumerator.Current; if (currentItem.CompareTo(oldItem) > 0) { subset.Add(currentItem); } else { yield return subset; subset = new List () { currentItem }; } oldItem = supersetEnumerator.Current; } yield return subset; }
编辑:进一步简化解决方案,仅使用一个枚举器。
我修改了你的代码,现在工作正常:
List data = new List { 1, 2, 1, 2, 3,3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 6 }; List> resultLists = new List>(); 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 ()); resultLists[count].Add(p); } } else { resultLists.Add(new List ()); resultLists[count].Add(p); } last = p; return true; }).ToList();
对于这样的事情,我通常不喜欢使用GroupBy
或实现结果的其他方法的解决方案。 原因是您永远不知道输入序列将持续多长时间,并且这些子序列的实现可能非常昂贵。
我喜欢在结果被提取时传输结果。 这允许IEnumerable
实现,其流结果通过您对该流的转换继续流式传输。
请注意,如果您不再遍历子序列并希望继续下一个序列,则此解决方案将不起作用; 如果这是一个问题,那么实现子序列的解决方案之一可能会更好。
但是,对于整个序列的仅向前迭代(这是最典型的用例),这将正常工作。
首先,让我们为我们的测试类设置一些助手:
private static IEnumerable CreateEnumerable (IEnumerable 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 (IEnumerable data, [CallerMemberName] string name = "") where T : IComparable { // Write the name. Debug.WriteLine("Case: " + name); // Cycle through the chunks. foreach (IEnumerable 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
上实现它们作为扩展方法; 这是第一个好处,因为它不需要物化序列(从技术上讲,其他解决方案都没有,但最好明确地说明这样)。
一,切入点:
public static IEnumerable> ChunkWhenNextSequenceElementIsNotGreater( this IEnumerable source) where T : IComparable { // Validate parameters. if (source == null) throw new ArgumentNullException("source"); // Call the overload. return source. ChunkWhenNextSequenceElementIsNotGreater( Comparer .Default.Compare); } public static IEnumerable> ChunkWhenNextSequenceElementIsNotGreater ( this IEnumerable source, Comparison 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
或提供Comparison
委托的内容; 这允许您想要执行比较的任何类型和任何类型的规则。
这是实施:
private static IEnumerable> ChunkWhenNextSequenceElementIsNotGreaterImplementation( this IEnumerable source, Comparison comparer) { // Validate parameters. Debug.Assert(source != null); Debug.Assert(comparer != null); // Get the enumerator. using (IEnumerator 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 ( enumerator, comparer); // Yield. yield return chunkEnumerator; // If the last move next returned false, then get out. if (!chunkEnumerator.LastMoveNext) yield break; } } }
值得注意的是:这使用另一个类ChunkWhenNextSequenceElementIsNotGreaterEnumerable
来处理枚举子序列。 该类将迭代IEnumerator
中从原始IEnumerable
调用获得的每个项,但将最后一次调用的结果存储到IEnumerator
。
存储该子序列生成器,并检查最后一次调用MoveNext
值以查看序列的结尾是否已被命中。 如果它有,那么它只是打破,否则,它移动到下一个块。
这是ChunkWhenNextSequenceElementIsNotGreaterEnumerable
:
internal class ChunkWhenNextSequenceElementIsNotGreaterEnumerable : IEnumerable { #region Constructor. internal ChunkWhenNextSequenceElementIsNotGreaterEnumerable( IEnumerator enumerator, Comparison 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 _enumerator; private readonly Comparison _comparer; internal bool LastMoveNext { get; private set; } #endregion #region IEnumerable implementation. public IEnumerator 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 { 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 { 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 { 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 { '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 }
您可以使用索引来使用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 => aG) .Select(g => g.Select(n => nN).ToArray()) .ToArray();
这是我使用一些产量的简单循环方法:
static IEnumerable
我使用字典获得5个不同的列表,如下所示;
static void Main(string[] args) { List data = new List { 1, 2, 1, 2, 3, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 6 }; Dictionary> listDict = new Dictionary>(); int listCnt = 1; //as initial value get first value from list listDict.Add(listCnt, new List ()); 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 ()); 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