Most evenly distribute letters of the alphabet across sequence

Question

I'm wondering if there is a sweet way I can do this in LINQ or something but I'm trying to most evenly distribute the letters of the alphabet across X parts where X is a whole number > 0 && <= 26. For example here might be some possible outputs.

• X = 1 : 1 partition of 26
• X = 2 : 2 partitions of 13
• X = 3 : 2 partitions of 9 and one partition of 8
• etc....

Ultimately I don't want to have any partitions that didn't end up getting at least one and I'm aiming to have them achieve the most even distribution that the range of difference between partition sizes is as small as posssible.

This is the code I tried orginally:

char[] alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".ToCharArray();
int pieces = (int)Math.Round((double)alphabet.Count() / numberOfParts); 
for (int i = 0; i < numberOfParts.Count; ++i) {
    char[] subset = i == numberOfParts.Count - 1 ? alphabet.Skip(i * pieces).ToArray()
                    : alphabet.Skip(i * pieces).Take(pieces).ToArray();
... // more code following

This seemed to be working fine at first but I realized in testing that there is a problem when X is 10. Based on this logic I'm getting 8 groups of 3 and one group of 2, leaving the 10th group 0 which is no good as I'm going for the most even distribution.

The most ideal distribution for 10 in this case would be 6 groupings of 3 and 4 groupings of 2. Any thoughts on how this might be implemented?

Answer 1

In general, the easiest way to implement the logic is using the modulo operator, %. Get familiar with this operator; it's very useful for the situations where it helps. There are a number of ways to write the actual code to do the distribution of letters, using arrays or not as you wish etc., but this short expression should give you an idea:

"ABCDEFGHIJKLMNOPQRSTUVWXYZ".IndexOf(letter) % partitionCount

This expression gives the zero-based index of the partition in which to deposit an upper-case letter. The string is just shown for convenience, but could be an array or some other way of representing the alphabet. You could loop over the alphabet, using logic similar to the above to choose where to deposit each letter. Up to you would be where to put the logic: inside a loop, in a method, etc.

There's nothing magical about modular arithmetic; it just "wraps around" after the end of the set of usable numbers is reached. A simple context in which we've all encountered this is in division; the % operator is essentially just giving a division remainder. Now that you understand what the % operator is doing, you could easily write your own code to do the same thing, in any language.

Putting this all together, you could write a utility, class or extension method like this one--note the % to calculate the remainder, and that simple integer division discards it:

/// <summary>
/// Returns partition sized which are as close as possible to equal while using the indicated total size available, with any extra distributed to the front
/// </summary>
/// <param name="totalSize">The total number of elements to partition</param>
/// <param name="partitionCount">The number of partitions to size</param>
/// <param name="remainderAtFront">If true, any remainder will be distributed linearly starting at the beginning; if false, backwards from the end</param>
/// <returns>An int[] containing the partition sizes</returns>
public static int[] GetEqualizedPartitionSizes(int totalSize, int partitionCount, bool remainderAtFront = true)
{
    if (totalSize < 1)
        throw new ArgumentException("Cannot partition a non-positive number (" + totalSize + ")");
    else if (partitionCount < 1)
        throw new ArgumentException("Invalid partition count (" + partitionCount + ")");
    else if (totalSize < partitionCount)
        throw new ArgumentException("Cannot partition " + totalSize + " elements into " + partitionCount + " partitions");

    int[] partitionSizes = new int[partitionCount];
    int basePartitionSize = totalSize / partitionCount;
    int remainder = totalSize % partitionCount;
    int remainderPartitionSize = basePartitionSize + 1;
    int x;

    if (remainderAtFront)
    {
        for (x = 0; x < remainder; x++)
            partitionSizes[x] = remainderPartitionSize;

        for (x = remainder; x < partitionCount; x++)
            partitionSizes[x] = basePartitionSize;
    }
    else
    {
        for (x = 0; x < partitionCount - remainder; x++)
            partitionSizes[x] = basePartitionSize;

        for (x = partitionCount - remainder; x < partitionCount; x++)
            partitionSizes[x] = remainderPartitionSize;
    }

    return partitionSizes;
}