Spread number of items equally across hours

Question

I have a variable number of items that I want to spread across a variable amount of hours. The issue I'm having is how to distribute the remainder so that the space between the "overhang" is as equal as possible. For example, if I have 13 items (X) spread across 5 hours I want to end up with

Hours:    1    2    3    4    5
---------------------------------
          x    x    x    x    x
          x    x    x    x    x  
          x         x         x

I'm not sure if I'm overthinking this. I'm currently checking if the number of items is greater than the number of hours. If that's true, I'm dividing (number of items/number of hours). Then I think that I have to divide (number of hours/remainder)... But for the above example: 5/3=1.6, which rounds to 2. I think that I have to use Math.Floor somehow, but I'm currently not really sure how.

For 4 items across 5 hours, I'd like to end up with the Xs For 2 items with the Ys For 1 item with the Zs

 1    2    3    4    5
------------------------
 x    x         x    x

      y         y

           z

The number of items and the number of hours are variable.

Okay, I think I'm currently on the right track. I'm now trying to split the bins in half and put one of the remainder in the center-bin. This repeats recursively until the remainder is 0.

Answer 1

EDIT: Fixed issue with even hours and items.

This is a hard problem and below is the solution. I've written solution for a completely generic problem so it works for arbitrary hours and number of items. Here's the example outputs:

Items=10, Hours=14
XX XX XX XX XX

Items=11, Hours=14
XX XXXXX XX XX

Items=12, Hours=14
XX XXXXXXXX XX

Items=16, Hours=13
XXXXXXXXXXXXX
     XXX

Items=17, Hours=13
XXXXXXXXXXXXX
X    X X    X

Items=18, Hours=13
XXXXXXXXXXXXX
X    XXX    X

Items=19, Hours=13
XXXXXXXXXXXXX
X X  X X  X X

Items=20, Hours=13
XXXXXXXXXXXXX
X X  XXX  X X

Items=21, Hours=13
XXXXXXXXXXXXX
X XX X X XX X

Here's how below solution works:

1. Number of filled lines are trivial which you can get it by (items/hours) * hours.
2. The last line is where all the magic is required.
3. When number of remaining items are odd we want to turn on the center. If number of hours are also odd then center is well defined but otherwise we are out of luck and we would have some "imbalance" in that case.
4. For even items we make them in to pairs and distribute each pair in the order of balanced binary tree. This basically means we first put each pair at the end. Then next pair half way through and recursively follow the pattern. This might be the most difficult part to understand so paper and pen is recommended :).

And here's the code:

static void Main(string[] args)
{
    var hours = 13;
    for (var items = 16; items < 22; items++)
        PrintDistribution(items, hours);
}

private static void PrintDistribution(int items, int hours)
{
    Console.WriteLine(string.Format("\nItems={0}, Hours={1}", items, hours));
    for (var i = 0; i < (items / hours) * hours; i++)
    {
        Console.Write('X');
        if ((i + 1) % hours == 0)
            Console.WriteLine();
    }

    var line = new StringBuilder(new string(' ', hours));
    var remaining = items % hours;
    var evens = remaining / 2;
    var odd = remaining - (evens * 2);
    var seq = BinaryTreeSequence(hours / 2).GetEnumerator();
    for (var i = 0; i < evens; i++)
    {
        seq.MoveNext();
        line[seq.Current] = 'X';
        line[hours - seq.Current - 1] = 'X';
    }

    if (odd > 0)
        if (hours % 2 == 0)
        {
            seq.MoveNext();
            line[seq.Current] = 'X';
        }
        else
            line[hours / 2] = 'X';

    Console.WriteLine(line);
}


public static IEnumerable<int> BinaryTreeSequence(int count)
{
    if (count > 1)
        yield return count - 1; 
    if (count > 0)
        yield return 0;

    var seqQueue = new Queue<Tuple<int, int, int>>();
    Enqueue(seqQueue, 0, count - 1);

    for (var seqIndex = count - 2; seqIndex > 0; seqIndex--)
    {
        var moreNeeded = seqQueue.Count < seqIndex;

        var seq = seqQueue.Dequeue();
        yield return seq.Item1;

        if (moreNeeded)
        {
            Enqueue(seqQueue, seq.Item1, seq.Item3);
            Enqueue(seqQueue, seq.Item2, seq.Item1);
        }
    }
}

private static void Enqueue(Queue<Tuple<int, int, int>> q, int min, int max)
{
    var midPoint = (min + max) / 2;
    if (midPoint != min && midPoint != max)
        q.Enqueue(Tuple.Create(midPoint, min, max));
}

Answer 2

Here's an approximate solution. It returns tuples with the zero-based index, and the item. (I assumed the items might be important, and not just dummy values like your xs) It doesn't choose the optimal spacing in some cases, but I think it'll always be close (i.e. gaps no more than 1 larger than necessary), and always return the correct number of items.

public static IEnumerable<Tuple<int, T>> SplitItems<T>(IEnumerable<T> items, int count)
{
    var itemList = items.ToList();
    int lastRowCount = itemList.Count % count;
    int wholeRowItemCount = itemList.Count - lastRowCount;

    // return full rows: 0 <= i < wholeRowCount * count
    for (int i = 0; i < wholeRowItemCount; i++)
    {
        yield return Tuple.Create(i % count, itemList[i]);
    }

    if (lastRowCount > 0)
    {
        //return final row: wholeRowCount * count <= i < itemList.Count
        double offset = (double)count / (lastRowCount + 1);
        for (double j = 0; j < lastRowCount; j++)
        {
            int thisIntPos = (int)Math.Round(j * count / (lastRowCount + 1) + offset, MidpointRounding.AwayFromZero);
            yield return Tuple.Create(thisIntPos, itemList[wholeRowItemCount + (int)j]);
        }
    }
}

As an example of how to use it:

Console.WriteLine(string.Join("\r\n", SplitItems(Enumerable.Range(1, 12), 5)));
// prints
(0, 1)
(1, 2)
(2, 3)
(3, 4)
(4, 5)
(0, 6)
(1, 7)
(2, 8)
(3, 9)
(4, 10)
(2, 11)
(3, 12)

(this is suboptimal because the last line has items at 2-3 and empty spaces/gaps at 0-1 and 4, while your solution with ys only has gaps of size 1)

Also, though it doesn't match your example (which would be 0, 2, 4 in my zero-based indexing), the following example satisfies the algorithm that you've defined so far, since it's minimized the gap size. (1-size gaps at indices 0 and 2, instead of yours, which has the gaps at 1 and 3) If 0, 2, 4 is indeed better than 1, 3, 4, you need to decide why exactly, and add that to your algorithm definition.

Console.WriteLine(string.Join("\r\n", SplitItems(Enumerable.Range(1, 3), 5)));
// prints
(1, 1)
(3, 2)
(4, 3)

Actually, this is a sort of restricted partition problem. For dividing d items across h hours, you want to find a partition of h-d with no more than h-d parts where max(parts) is the smallest it can be. E.g. dividing 2 items among 5 hours: the optimal solution is 1+1+1, because it has no more than 3 parts, and max(parts) == 1, which is the best you can do. As an example without a single solution, 3 items among 5 hours has 1+1, but there are different ways to arrange it, including 0,2,4, 1,3,4, and 0,2,3.