The most evenly distributed letters of the alphabet in sequence

Question

I am wondering if there is a sweet way I can do in LINQ or something like that, but I'm trying to distribute the letters of the alphabet as evenly as possible in X parts, where X is an integer> 0 && <= 26. For example, here can there are some possible exits.

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

Ultimately, I do not want to have any partitions that do not end with at least one, and I want them to achieve the most even distribution, that the range of differences between the sizes of the partitions is as small as possible.

This is the code I tried originally:

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 

It seemed that at first everything worked fine, but I realized that there is a problem when X is 10. Based on this logic, I get 8 groups of 3 and one group of 2, leaving the 10th group 0, which is not good, because I am going for the most even distribution.

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

Answer 1

In general, the easiest way to implement logic is to use the modulo operator,%. Get to know this operator; It is very useful for situations where it helps. There are several ways to write the actual code to distribute letters, whether to use arrays or not, as you wish, etc., but this short expression should give you an idea:

 "ABCDEFGHIJKLMNOPQRSTUVWXYZ".IndexOf(letter) % partitionCount 

This expression gives an index based on the zero value of the section in which to capitalize the letter. The string is just shown for convenience, but may be an array or some other way of representing the alphabet. You can iterate over the alphabet using logic similar to the one above to choose where to place each letter. Before you could put the logic: inside the loop, in the method, etc.

There is nothing magical about modular arithmetic; it just “wraps around” after reaching the set of available numbers. The simple context in which we all meet this is separation; the% operator, in fact, just gives the remainder of the division. Now that you understand what the% operator does, you can easily write your own code to do the same in any language.

Combining all this, you can write a utility, class, or extension method like this — pay attention to% to calculate the remainder, and this 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; } 

Answer 2

It seems to me that the easiest way to achieve this is to perform a circular distribution of each letter. Loop each letter of the alphabet and add to it, then repeat. You have a counter that determines which letter you will place your item on, and then when it reaches 26, reset, it will return to 0!

Answer 3

What I did in one application that I needed to distribute 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 will not give you the exact result that you expected (i.e. the ideal result for 10 sections), but it is pretty close.

ps this is not verified :)

Answer 4

The pseudo-code algorithm I was testing now:

 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 ranges.Add

_{Here is the implementation of this LinqPad VB.NET algorithm.}

Thus, the Linq version will be similar to

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

_{Here is the LinqPad VB.NET implementation using this Linq query.}

Answer 5

(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 name it like this:

 var result = alphabet.Batch((int)Math.Ceiling(x / 26.0));