“公平地”对结果进行分组使用LINQ

Question

我有一个系统用户列表，正在等待分配帐户。
分配算法非常简单，分配应该尽可能公平，这意味着如果我有 40 个帐户和 20 个系统用户，我需要为每个系统用户分配 2 个帐户。
如果我有 41 个帐户和 20 个系统用户，我需要为每个系统用户分配 2 个帐户，并再次在系统用户之间拆分剩余帐户（在这种情况下，将为一个系统用户分配一个额外帐户）。
我试图弄清楚如何在使用 LINQ 查询时执行此操作。
到目前为止，我认为应该涉及分组，我的查询如下：

from account in accounts
    let accountsPerSystemUser = accounts.Count / systemUsers.Count
    let leftover = accounts.Count % systemUsers.Count
    from systemUser in systemUsers
        group account by systemUser into accountsGroup
select accountsGroup

但是我不确定如何从这里继续。
我确信我在这里缺少一个 where 子句，如果您达到了分配给系统用户的最大帐户数量，该子句将阻止分组。 如何正确实现查询以便分组知道分配多少？

Answer 1

这是一个简单的实现，如果您可以将自己限制为 accounts 的 IList（不过您始终可以使用 ToList），那么该实现就可以工作。 。

public static IEnumerable<IGrouping<TBucket, TSource>> DistributeBy<TSource, TBucket>(
    this IEnumerable<TSource> source, IList<TBucket> buckets)
{
    var tagged = source.Select((item,i) => new {item, tag = i % buckets.Count});
    var grouped = from t in tagged
                  group t.item by buckets[t.tag];
    return grouped;
}

// ...
var accountsGrouped = accounts.DistributeBy(systemUsers);

基本上，这会获取每个帐户的索引并“标记”每个帐户，并将该索引的整数除以系统用户数的余数。这些标签是它们所属的系统用户的索引。然后它只是按该索引处的系统用户对它们进行分组。

这可以确保您的公平性要求，因为余数将在零和一减去系统用户数之间循环。

0 % 20 = 0
1 % 20 = 1
2 % 20 = 2
...
19 % 20 = 19
20 % 20 = 0
21 % 21 = 1
22 % 22 = 2
...
39 % 20 = 19
40 % 20 = 0

Answer 2

您无法使用“纯 LINQ”（即使用查询理解语法）来做到这一点，而且说实话，LINQ 可能不是最好的方法。尽管如此，这里还是一个如何执行此操作的示例：

var listB = new List<string>() { "a", "b", "c", "d", "e" };
var listA = new List<string>() { "1", "2", "3" };

var groupings = (from b in listB.Select((b, i) => new
                                        {
                                            Index = i,
                                            Element = b
                                        })
                 group b.Element by b.Index % listA.Count).Zip(listA, (bs, a) => new
                                                                      {
                                                                          A = a,
                                                                          Bs = bs
                                                                      });

foreach (var item in groupings)
{
    Console.WriteLine("{0}: {1}", item.A, string.Join(",", item.Bs));
}

输出：

1: a,d
2: b,e
3: c

Answer 3

我不认为“纯”LINQ 真的适合解决这个问题。不过，这里有一个只需要两个 IEnumerable 的解决方案：

var users = new[] { "A", "B", "C" };
var accounts = new[] { 1, 2, 3, 4, 5, 6, 7, 8 };
var accountsPerUser = accounts.Count()/users.Count();
var leftover = accounts.Count()%users.Count();
var assignments = users
  .Select((u, i) => new {
    User = u,
    AccountsToAssign = accountsPerUser + (i < leftover ? 1 : 0),
    AccountsAlreadyAssigned =
      (accountsPerUser + 1)*(i < leftover ? i : leftover)
      + accountsPerUser*(i < leftover ? 0 : i - leftover)
  })
  .Select(x => new {
    x.User,
    Accounts = accounts
      .Skip(x.AccountsAlreadyAssigned)
      .Take(x.AccountsToAssign)
  });

为了减少文本，我使用术语 User 而不是 SystemUser。

这个想法很简单。第一个剩余用户将从accounts分配accountsPerUser + 1。其余用户仅分配到 accountsPerUser。

第一个 Select 使用提供索引的重载来计算这些值：

User | Index | AccountsAlreadyAssigned | AccountsToAssign
-----+-------+-------------------------+-----------------
A    | 0     | 0                       | 3
B    | 1     | 3                       | 3
C    | 1     | 6                       | 2

第二个 Select 使用这些值来 Skip 和 Take< /code> 来自帐户的正确号码。

如果您愿意，可以“合并”两个 Select 语句，并将 AccountsAlreadyAssigned 和 AccountsToAssign 替换为用于计算它们的表达式。然而，这将使查询变得非常难以理解。

这是一个“非 LINQ”替代方案。它基于 IList，但可以轻松转换为 IEnumerable。或者，它可以在循环内执行分配，而不是将分配作为元组返回。

IEnumerable<Tuple<T, IList<U>>> AssignEvenly<T, U>(IList<T> targetItems, IList<U> sourceItems) {
  var fraction = sourceItems.Count/targetItems.Count;
  var remainder = sourceItems.Count%targetItems.Count;
  var sourceIndex = 0;
  for (var targetIndex = 0; targetIndex < targetItems.Count; ++targetIndex) {
    var itemsToAssign = fraction + (targetIndex < remainder ? 1 : 0);
    yield return Tuple.Create(
      targetItems[targetIndex],
      (IList<U>) sourceItems.Skip(sourceIndex).Take(itemsToAssign).ToList()
    );
    sourceIndex += itemsToAssign;
  }
}