使用 LINQ 按最大组大小按不等式对 C# 集合进行分组
Group a C# collection by inequality with a maximum group size using LINQ
问题
我正在尝试获取对象集合并将其拆分为多个子集合（使用 LINQ），其中：
- 没有子集合包含根据某些任意标准相等的两个对象（在示例中，没有两个对象可以具有相同的 GroupId）。
- 没有子集合的元素数超过最大数量。
- 尽量减少子集合的数量（每个子集合在满足1和2的情况下尽量满）
你试过什么？
到目前为止，我已经尝试使用 LINQ 的聚合函数，以及 MoreLinq 的批处理、分区、DictinctBy 和其他一些函数。 None 其中似乎完全符合我的要求。我还有一个不专门使用 LINQ 的工作解决方案。我希望有一个利用 LINQ 的相当简单的解决方案。
代码示例
Here是不使用LINQ的例子
using System.Collections.Generic;
using System.Linq;
public class Program
{
public static void Main()
{
var records = new List<Foo>() {
new Foo(1, 1),
new Foo(2, 1),
new Foo(3, 1),
new Foo(4, 2),
new Foo(5, 2),
new Foo(6, 3),
new Foo(7, 4),
new Foo(8, 5),
new Foo(9, 6),
new Foo(10, 7),
};
var groups = Group(records, 3);
for (int i = 0; i < groups.Count(); ++i) {
System.Console.WriteLine($"Group {i}: {Newtonsoft.Json.JsonConvert.SerializeObject(groups[i])}");
}
}
public class Foo {
public int Id;
public int GroupId;
public Foo(int id, int groupId) {
this.Id = id;
this.GroupId = groupId;
}
}
public static List<List<Foo>> Group(IEnumerable<Foo> records, int maxGroupSize)
{
var rv = new List<List<Foo>>();
foreach (var record in records) {
bool added = false;
for (int i = 0; i < rv.Count; ++i) {
if (rv[i].Count < maxGroupSize && !rv[i].Any(a => a.GroupId == record.GroupId)) {
rv[i].Add(record);
added = true;
break;
}
}
if (!added) {
rv.Add(new List<Foo>() { record });
}
}
return rv;
}
}
我不只是在寻找更有效的上述实现。这只是 a 解决方案的一个示例。我正在寻找一种利用 LINQ 的解决方案。
是的，使用纯 LINQ 是可行的。
如果没有第三个要求，它是非常微不足道的，但是那个会引发一个怪癖。下面的代码实现了所有三个要求，AFAICT，演示在 https://dotnetfiddle.net/hwECKG.
代码中的注释解释了如何获得结果。
可能有优化的机会，但这超出了问题的范围。
using System.Collections.Generic;
using System.Linq;
public class Program
{
public static void Main()
{
var records = new List<Foo>() {
new Foo(1, 1),
new Foo(2, 1),
new Foo(3, 1),
new Foo(4, 2),
new Foo(5, 2),
new Foo(6, 3),
new Foo(7, 4),
new Foo(8, 5),
new Foo(9, 6),
new Foo(10, 7),
};
const int maxPerGroup = 3;
var groups = records
// Find and group all the Foo's that cannot be in the same collection.
.GroupBy(r => r.GroupId)
// For each Foo with the same Group id, assign an index by its position.
// This will be used in the next step to assign same-groupid foos to different buckets.
.SelectMany(g => g.Select((r, i) => new {
Bucket = i,
Record = r
}))
// As mentioned above, assign phobic Foos to different buckets.
.GroupBy(g => g.Bucket, p => p.Record)
// Below is not *technically* necessary if `records` enumerable can be enumerated multiple times,
// but I don't make that assumption. This converts items to an array so we can enumerate it more than once below.
.Select(g => g.ToArray())
// Now take each bucket and split it into members that fit and overflows, if any.
.Select(b => new {
Members = b.Take(maxPerGroup),
Overflows = b.Skip(maxPerGroup)
})
// Via aggregation, go thru all buckets keeping them, but picking off their overflows into one signle overflow collection.
// Further processing is actually nexted in projection argument of the aggregate since
// aggregate wants to return a single item, and that's not what we need.
.Aggregate(
new { Groups = new List<IEnumerable<Foo>>(), Overflows = new Queue<Foo>()},
(acc, next) => {
acc.Groups.Add(next.Members);
foreach(var o in next.Overflows)
acc.Overflows.Enqueue(o);
return acc;
},
// Here we have all buckets and a single overflow queue, now go thru each bucket and fill it up from overflow if it has any space left.
t => t.Groups.Aggregate(
new { Groups = new List<IEnumerable<Foo>>(), Overflows = t.Overflows },
(dist, next) => {
var currentGroupMembers = next.ToList();
while (currentGroupMembers.Count() < maxPerGroup && dist.Overflows.Count > 0)
currentGroupMembers.Add(dist.Overflows.Dequeue());
dist.Groups.Add(currentGroupMembers);
return dist;
},
// And by the time we get here, we filled all existing buckets, but may have things left in overflow.
// So just chunk up overflow and add it to our list of buckets.
t2 => {
t2.Groups.AddRange(t2.Overflows.Chunk(maxPerGroup));
// And that returns the final result.
return t2.Groups;
}
)
)
// This is not really necessary, but helps to see in memory with debugging.
.ToArray();
for (int i = 0; i < groups.Count(); ++i) {
System.Console.WriteLine($"Group {i}: {Newtonsoft.Json.JsonConvert.SerializeObject(groups[i])}");
}
}
public class Foo {
public int Id;
public int GroupId;
public Foo(int id, int groupId) {
this.Id = id;
this.GroupId = groupId;
}
}
}
编辑：
我应该在发布时添加以下内容。我试图尽可能接近“使用 LINQ”的合理解释，这意味着尝试在一个连续的 LINQ 链中完成整个事情，并且做（几乎，例外是几个 foreach 循环可能可以避免，但方式太痛苦）所有计算都使用 LINQ 函数。
但可以简化。
最可怕的事情是对 .Aggregate 的调用，它是高效的，但是 scary-looking 由于必须将其嵌套在投影参数中。简单地获取第一个 .Aggregate 没有投影参数，并将 return 保存到局部变量会更容易。 return 将有一个包含组和单个溢出列表的对象。然后，您可以在溢出时调用 .GetEnumerator()，然后一个简单的循环可以轻松地遍历每个组并通过使用枚举器“填充”它，然后在必要时使用块。该代码看起来会更短（尽管做同样的事情），但可能不符合 OP 对它是“LINQ”的要求。
通过创建 LINQ 扩展方法来轻松执行一些自定义步骤，香草 LINQ 使它变得更难，其他简化是可能的。出于挑战的目的，我没有这样做，但根据自己的经验，这也有助于简化代码（并且仍然是“LINQ”）。
此外，我应该指出，我的演示并不是要展示“LINQ 的最有效使用”，而是要挑战在 LINQ 中做到这一点（我知道这是可能的）。这段代码可能可以简化，我欢迎任何人试一试——我只是没有时间也让答案解决方案更“优雅”。
但是对于说它太复杂的评论——这要视情况而定。我们不知道为什么 OP 要在 LINQ 中使用它。 LINQ 往往会变得更高效，因为它往往会避免额外的数据复制和移动。或者 OP 可能希望将其插入更大的 LINQ-based 基础架构，因此希望获得 IEnumerable 以在 LINQ 基础架构中进行更多处理。我曾经处理过 reporting-like 问题，其中 LINQ 链是根据参数以编程方式生成的，并在得到最终答案之前进行了 25 次以上的转换，但它有效地工作，最大限度地减少了数据复制操作，并允许它插入一个通用的数据的消费者。
更新 2
所以这是一个较短的版本，但 LINQy 少了一点，尽管仍然非常多地使用 LINQ 来解决问题：https://dotnetfiddle.net/n9Fz6K
不确定它看起来是否不那么可怕，也不确定哪个表现更好。但是肯定有不止一种方法可以做到这一点，而且是可能的。
LINQ 需要时间来习惯，阅读代码可能有点像阅读 SQL —— 必须从“数据集”而不是单个数据记录中思考。但是一旦你掌握了它，它比 old-school 方式更容易阅读和理解 :D.
using System.Collections.Generic;
using System.Linq;
public class Program
{
public static void Main()
{
var records = new List<Foo>() {
new Foo(1, 1),
new Foo(2, 1),
new Foo(3, 1),
new Foo(4, 2),
new Foo(5, 2),
new Foo(6, 3),
new Foo(7, 4),
new Foo(8, 5),
new Foo(9, 6),
new Foo(10, 7),
};
const int maxPerGroup = 3;
var groupAssigns = records
// Find and group all the Foo's that cannot be in the same collection.
.GroupBy(r => r.GroupId)
// For each Foo with the same Group id, assign an index by its position.
// This will be used in the next step to assign same-groupid foos to different buckets.
.SelectMany(g => g.Select((r, i) => new {
Bucket = i,
Record = r
}))
// As mentioned above, assign phobic Foos to different buckets.
.GroupBy(g => g.Bucket, p => p.Record)
// Now take each bucket and split it into members that fit and overflows, if any.
.Select(b => b.Chunk(maxPerGroup).ToArray())
.Select(b => new {
Group = b[0],
Overflows = b.Skip(1).SelectMany(c => c)
})
.Aggregate(
new { Groups = new List<List<Foo>>(), Overflows = new Queue<Foo>()},
(acc, next) => {
acc.Groups.Add(next.Group.ToList());
foreach(var o in next.Overflows)
acc.Overflows.Enqueue(o);
return acc;
}
);
var groups = groupAssigns.Groups;
foreach(var g in groups)
{
while(g.Count() < maxPerGroup && groupAssigns.Overflows.Count > 0)
g.Add(groupAssigns.Overflows.Dequeue());
}
groups.AddRange(groupAssigns.Overflows.Chunk(maxPerGroup).Select(c => c.ToList()));
for (int i = 0; i < groups.Count(); ++i) {
System.Console.WriteLine($"Group {i}: {Newtonsoft.Json.JsonConvert.SerializeObject(groups[i])}");
}
}
public class Foo {
public int Id;
public int GroupId;
public Foo(int id, int groupId) {
this.Id = id;
this.GroupId = groupId;
}
}
}
问题
我正在尝试获取对象集合并将其拆分为多个子集合（使用 LINQ），其中：
- 没有子集合包含根据某些任意标准相等的两个对象（在示例中，没有两个对象可以具有相同的 GroupId）。
- 没有子集合的元素数超过最大数量。
- 尽量减少子集合的数量（每个子集合在满足1和2的情况下尽量满）
你试过什么？
到目前为止，我已经尝试使用 LINQ 的聚合函数，以及 MoreLinq 的批处理、分区、DictinctBy 和其他一些函数。 None 其中似乎完全符合我的要求。我还有一个不专门使用 LINQ 的工作解决方案。我希望有一个利用 LINQ 的相当简单的解决方案。
代码示例
Here是不使用LINQ的例子
using System.Collections.Generic;
using System.Linq;
public class Program
{
public static void Main()
{
var records = new List<Foo>() {
new Foo(1, 1),
new Foo(2, 1),
new Foo(3, 1),
new Foo(4, 2),
new Foo(5, 2),
new Foo(6, 3),
new Foo(7, 4),
new Foo(8, 5),
new Foo(9, 6),
new Foo(10, 7),
};
var groups = Group(records, 3);
for (int i = 0; i < groups.Count(); ++i) {
System.Console.WriteLine($"Group {i}: {Newtonsoft.Json.JsonConvert.SerializeObject(groups[i])}");
}
}
public class Foo {
public int Id;
public int GroupId;
public Foo(int id, int groupId) {
this.Id = id;
this.GroupId = groupId;
}
}
public static List<List<Foo>> Group(IEnumerable<Foo> records, int maxGroupSize)
{
var rv = new List<List<Foo>>();
foreach (var record in records) {
bool added = false;
for (int i = 0; i < rv.Count; ++i) {
if (rv[i].Count < maxGroupSize && !rv[i].Any(a => a.GroupId == record.GroupId)) {
rv[i].Add(record);
added = true;
break;
}
}
if (!added) {
rv.Add(new List<Foo>() { record });
}
}
return rv;
}
}
我不只是在寻找更有效的上述实现。这只是 a 解决方案的一个示例。我正在寻找一种利用 LINQ 的解决方案。
是的，使用纯 LINQ 是可行的。
如果没有第三个要求，它是非常微不足道的，但是那个会引发一个怪癖。下面的代码实现了所有三个要求，AFAICT，演示在 https://dotnetfiddle.net/hwECKG.
代码中的注释解释了如何获得结果。
可能有优化的机会，但这超出了问题的范围。
using System.Collections.Generic;
using System.Linq;
public class Program
{
public static void Main()
{
var records = new List<Foo>() {
new Foo(1, 1),
new Foo(2, 1),
new Foo(3, 1),
new Foo(4, 2),
new Foo(5, 2),
new Foo(6, 3),
new Foo(7, 4),
new Foo(8, 5),
new Foo(9, 6),
new Foo(10, 7),
};
const int maxPerGroup = 3;
var groups = records
// Find and group all the Foo's that cannot be in the same collection.
.GroupBy(r => r.GroupId)
// For each Foo with the same Group id, assign an index by its position.
// This will be used in the next step to assign same-groupid foos to different buckets.
.SelectMany(g => g.Select((r, i) => new {
Bucket = i,
Record = r
}))
// As mentioned above, assign phobic Foos to different buckets.
.GroupBy(g => g.Bucket, p => p.Record)
// Below is not *technically* necessary if `records` enumerable can be enumerated multiple times,
// but I don't make that assumption. This converts items to an array so we can enumerate it more than once below.
.Select(g => g.ToArray())
// Now take each bucket and split it into members that fit and overflows, if any.
.Select(b => new {
Members = b.Take(maxPerGroup),
Overflows = b.Skip(maxPerGroup)
})
// Via aggregation, go thru all buckets keeping them, but picking off their overflows into one signle overflow collection.
// Further processing is actually nexted in projection argument of the aggregate since
// aggregate wants to return a single item, and that's not what we need.
.Aggregate(
new { Groups = new List<IEnumerable<Foo>>(), Overflows = new Queue<Foo>()},
(acc, next) => {
acc.Groups.Add(next.Members);
foreach(var o in next.Overflows)
acc.Overflows.Enqueue(o);
return acc;
},
// Here we have all buckets and a single overflow queue, now go thru each bucket and fill it up from overflow if it has any space left.
t => t.Groups.Aggregate(
new { Groups = new List<IEnumerable<Foo>>(), Overflows = t.Overflows },
(dist, next) => {
var currentGroupMembers = next.ToList();
while (currentGroupMembers.Count() < maxPerGroup && dist.Overflows.Count > 0)
currentGroupMembers.Add(dist.Overflows.Dequeue());
dist.Groups.Add(currentGroupMembers);
return dist;
},
// And by the time we get here, we filled all existing buckets, but may have things left in overflow.
// So just chunk up overflow and add it to our list of buckets.
t2 => {
t2.Groups.AddRange(t2.Overflows.Chunk(maxPerGroup));
// And that returns the final result.
return t2.Groups;
}
)
)
// This is not really necessary, but helps to see in memory with debugging.
.ToArray();
for (int i = 0; i < groups.Count(); ++i) {
System.Console.WriteLine($"Group {i}: {Newtonsoft.Json.JsonConvert.SerializeObject(groups[i])}");
}
}
public class Foo {
public int Id;
public int GroupId;
public Foo(int id, int groupId) {
this.Id = id;
this.GroupId = groupId;
}
}
}
编辑：
我应该在发布时添加以下内容。我试图尽可能接近“使用 LINQ”的合理解释，这意味着尝试在一个连续的 LINQ 链中完成整个事情，并且做（几乎，例外是几个 foreach 循环可能可以避免，但方式太痛苦）所有计算都使用 LINQ 函数。
但可以简化。
最可怕的事情是对 .Aggregate 的调用，它是高效的，但是 scary-looking 由于必须将其嵌套在投影参数中。简单地获取第一个 .Aggregate 没有投影参数，并将 return 保存到局部变量会更容易。 return 将有一个包含组和单个溢出列表的对象。然后，您可以在溢出时调用 .GetEnumerator()，然后一个简单的循环可以轻松地遍历每个组并通过使用枚举器“填充”它，然后在必要时使用块。该代码看起来会更短（尽管做同样的事情），但可能不符合 OP 对它是“LINQ”的要求。
通过创建 LINQ 扩展方法来轻松执行一些自定义步骤，香草 LINQ 使它变得更难，其他简化是可能的。出于挑战的目的，我没有这样做，但根据自己的经验，这也有助于简化代码（并且仍然是“LINQ”）。
此外，我应该指出，我的演示并不是要展示“LINQ 的最有效使用”，而是要挑战在 LINQ 中做到这一点（我知道这是可能的）。这段代码可能可以简化，我欢迎任何人试一试——我只是没有时间也让答案解决方案更“优雅”。
但是对于说它太复杂的评论——这要视情况而定。我们不知道为什么 OP 要在 LINQ 中使用它。 LINQ 往往会变得更高效，因为它往往会避免额外的数据复制和移动。或者 OP 可能希望将其插入更大的 LINQ-based 基础架构，因此希望获得 IEnumerable 以在 LINQ 基础架构中进行更多处理。我曾经处理过 reporting-like 问题，其中 LINQ 链是根据参数以编程方式生成的，并在得到最终答案之前进行了 25 次以上的转换，但它有效地工作，最大限度地减少了数据复制操作，并允许它插入一个通用的数据的消费者。
更新 2
所以这是一个较短的版本，但 LINQy 少了一点，尽管仍然非常多地使用 LINQ 来解决问题：https://dotnetfiddle.net/n9Fz6K
不确定它看起来是否不那么可怕，也不确定哪个表现更好。但是肯定有不止一种方法可以做到这一点，而且是可能的。
LINQ 需要时间来习惯，阅读代码可能有点像阅读 SQL —— 必须从“数据集”而不是单个数据记录中思考。但是一旦你掌握了它，它比 old-school 方式更容易阅读和理解 :D.
using System.Collections.Generic;
using System.Linq;
public class Program
{
public static void Main()
{
var records = new List<Foo>() {
new Foo(1, 1),
new Foo(2, 1),
new Foo(3, 1),
new Foo(4, 2),
new Foo(5, 2),
new Foo(6, 3),
new Foo(7, 4),
new Foo(8, 5),
new Foo(9, 6),
new Foo(10, 7),
};
const int maxPerGroup = 3;
var groupAssigns = records
// Find and group all the Foo's that cannot be in the same collection.
.GroupBy(r => r.GroupId)
// For each Foo with the same Group id, assign an index by its position.
// This will be used in the next step to assign same-groupid foos to different buckets.
.SelectMany(g => g.Select((r, i) => new {
Bucket = i,
Record = r
}))
// As mentioned above, assign phobic Foos to different buckets.
.GroupBy(g => g.Bucket, p => p.Record)
// Now take each bucket and split it into members that fit and overflows, if any.
.Select(b => b.Chunk(maxPerGroup).ToArray())
.Select(b => new {
Group = b[0],
Overflows = b.Skip(1).SelectMany(c => c)
})
.Aggregate(
new { Groups = new List<List<Foo>>(), Overflows = new Queue<Foo>()},
(acc, next) => {
acc.Groups.Add(next.Group.ToList());
foreach(var o in next.Overflows)
acc.Overflows.Enqueue(o);
return acc;
}
);
var groups = groupAssigns.Groups;
foreach(var g in groups)
{
while(g.Count() < maxPerGroup && groupAssigns.Overflows.Count > 0)
g.Add(groupAssigns.Overflows.Dequeue());
}
groups.AddRange(groupAssigns.Overflows.Chunk(maxPerGroup).Select(c => c.ToList()));
for (int i = 0; i < groups.Count(); ++i) {
System.Console.WriteLine($"Group {i}: {Newtonsoft.Json.JsonConvert.SerializeObject(groups[i])}");
}
}
public class Foo {
public int Id;
public int GroupId;
public Foo(int id, int groupId) {
this.Id = id;
this.GroupId = groupId;
}
}
}