Grouping results "fairly" using LINQ

Question

I have a list of system users that are awaiting to be assigned with an account.
The assignment algorithm is very simple, assigning should be as fair as possible which means that if I have 40 accounts and 20 system users I need to assign 2 accounts per system user.
If I have 41 accounts and 20 system users I need to assign 2 accounts per system user and split the remaining accounts between the system users again (in this case, one system user will be assigned with one extra account).
I am trying to figure out how to do this while using a LINQ query.
So far I figured that grouping should be involved and my query is the following:

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

However I am uncertain how to proceed from here.
I am positive that I am missing a where clause here that will prevent grouping if you reached the maximum amount of accounts to be assigned to a system user. How do I implement the query correctly so that the grouping will know how much to assign?

Answer 1

I don't thin "pure" LINQ is really suited to solve this problem. Nevertheless here is a solution that only requires two 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)
  });

To cut down on the text I use the term User instead of SystemUser.

The idea is quite simple. The first leftover users are assigned accountsPerUser + 1 from accounts. The remaining users are only assigned accountsPerUser.

The first Select uses the overload that provides an index to compute these values:

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

The second Select uses these values to Skip and Take the correct numbers from accounts.

If you want to you can "merge" the two Select statements and replace the AccountsAlreadyAssigned and AccountsToAssign with the expressions used to compute them. However, that will make the query really hard to understand.

Here is a "non-LINQ" alternative. It is based on IList but could easily be converted to IEnumerable. Or instead of returning the assignments as tuples it could perform the assignments inside the loop.

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;
  }
}

Answer 2

Here is a simple implementation that works if you can restrict yourself to a IList<T> for the accounts (you can always use ToList though).

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);

Basically this grabs each account's index and "tags" each with the remainder of integer division of that index by the number of system users. These tags are the indices of the system users they will belong to. Then it just groups them by the system user at that index.

This ensures your fairness requirement because the remainder will cycle between zero and one minus the number of system users.

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 3

You can't do this using "pure LINQ" (i.e. using query comprehension syntax), and to be honest LINQ probably isn't the best approach here. Nonetheless, here's an example of how you might do it:

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));
}

This outputs:

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