4

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?

Jesse Carter
  • 20,062
  • 7
  • 64
  • 101
  • Your question sounds very specific and unclear, can you elaborate what you're trying to achieve here ? Also is this coursework? That's not a problem if it is, but it's good to tell us as it might affect the answer you get! – Russ Clarke May 30 '13 at 01:13
  • No this isn't homework at all I'm trying to distribute messages to different locations based on the starting letter. – Jesse Carter May 30 '13 at 01:14
  • Fair enough - Can you elaborate as to the why? I have a feeling there's a clever answer and a good answer here! – Russ Clarke May 30 '13 at 01:31
  • There's some great awnser here: http://stackoverflow.com/questions/1450774/splitting-a-string-into-chunks-of-a-certain-size – the_lotus May 30 '13 at 01:55

5 Answers5

3

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;
}
Iucounu
  • 1,630
  • 1
  • 20
  • 31
  • Note that, as it stands, this answer puts 'A' and 'B' in separate groups once you have more than one group. The original question and other answers are attempting to partition consecutive indexes, like pagination. – Mark Hurd Jun 01 '13 at 05:50
2

I feel like the simplest way to achieve this is to perform a round robin distribution on each letter. Cycle through each letter of the alphabet and add to it, then repeat. Have a running count that determines what letter you will be putting your item in, then when it hits >26, reset it back to 0!

Jason Higgins
  • 1,516
  • 1
  • 17
  • 37
  • Up-voted for extreme conceptual simplicity. With a routine like this performance would generally not be an issue, and there's a lot to be said for a KISS approach in general. – Iucounu Jun 22 '13 at 11:50
1

What I did in one app I had to distribute things in groups was something like this

var numberOfPartitions = GetNumberOfPartitions();
var numberOfElements = GetNumberOfElements();

while (alphabet.Any())
{
     var elementsInCurrentPartition = Math.Ceil((double)numberOfPartitions / numberOfElements) 

     for (int i = 0; i < elementsInCurrentPartition; i++)
     {
          //fill your partition one element at a time and remove the element from the alphabet
          numberOfElements--;
     }
     numberOfPartitions--;
}

This won't give you the exact result you expected (i.e. ideal result for 10 partitions) but it's pretty close.

p.s. this isn't tested :)

Ivan Crojach Karačić
  • 1,911
  • 2
  • 24
  • 44
1

A pseudocode algorithm I have now tested:

Double count = alphabet.Count()
Double exact = count / numberOfParts
Double last = 0.0
Do Until last >= count
  Double next = last + exact
  ranges.Add alphabet, from:=Round(last), to:=Round(next)
  last = next
Loop

ranges.Add can ignore empty ranges :-)

Here is a LinqPad VB.NET implementation of this algorithm.

So a Linq version of this would be something like

Double count = alphabet.Count();
Double exact = count / numberOfParts;

var partitions = Enumerable.Range(0, numberOfParts + 1).Select(n => Round((Double)n * exact));

Here is a LinqPad VB.NET implementation using this Linq query.

Mark Hurd
  • 10,665
  • 10
  • 68
  • 101
0

(sorry for formatting, mobile)

First, you need something like a batch method:

public static IEnumerable<IEnumerable<T>> Batch<T>(this IEnumerable<T> source, int groupSize)
{
    var tempSource = source.Select(n => n);
    while (tempSource.Any())
    {
        yield return tempSource.Take(groupSize);
        tempSource = tempSource.Skip(groupSize);
    }
}

Then, just call it like this:

var result = alphabet.Batch((int)Math.Ceiling(x / 26.0));
It'sNotALie.
  • 22,289
  • 12
  • 68
  • 103