Распространение количества позиций в равном количестве часов

Question

У меня есть переменное количество элементов, которые я хочу распространять на переменное количество часов. Проблема, с которой я сталкиваюсь, заключается в том, как распределить остаток, чтобы пространство между «свесом» было как можно более равным. Например, если у меня есть 13 пунктов (X) распространения через 5 часов я хочу закончить с

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

Я не уверен, если я overthinking это. В настоящее время я проверяю, больше ли количество элементов, чем количество часов. Если это правда, я разделяю (количество элементов/количество часов). Затем я думаю, что мне нужно разделить (количество часов/остаток) ... Но для приведенного выше примера: 5/3 = 1,6, который округляется до 2. Я думаю, что я должен использовать Math.Floor как-то, но я сейчас не совсем уверен, как.

В течение 4 элементов через 5 часов, я хотел бы в конечном итоге с Xs 2 предметов с Ys Для 1 пункта с Zs

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

     y   y 

      z 

Число элементов и числом часы являются переменными.

Хорошо, я думаю, что сейчас я на правильном пути. Теперь я пытаюсь разбить ящики пополам и положить один из остатков в центр-бункер. Это повторяется рекурсивно, пока остаток не равен 0.

Answer 1

EDIT: Исправлена ​​проблема с четными часами и пунктами.

Это трудная проблема, и ниже это решение. Я написал решение для полностью общей проблемы, поэтому он работает для произвольных часов и количества элементов. Вот примерные результаты:

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 

Вот как ниже решение работает:

1. Количество заполненных строк тривиальны, которые вы можете получить его (пункты/ч) * часов.
2. Последняя строка, где требуется вся магия.
3. Когда количество оставшихся предметов нечетное, мы хотим включить центр. Если количество часов также нечетное, то центр четко определен, но в противном случае нам не повезло, и в этом случае у нас будет некоторый «дисбаланс».
4. Для четных элементов мы делаем их для пар и распределяем каждую пару в порядке сбалансированного двоичного дерева. Это в основном означает, что мы сначала помещаем каждую пару в конец. Затем следующая пара проходит на полпути и рекурсивно следит за рисунком. Это может быть самой трудной частью для понимания, поэтому рекомендуется бумага и ручка :).

А вот код:

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

Вот приближенное решение. Он возвращает кортежи с индексом на основе нуля и элементом. (Я предположил, что элементы могут быть важны, а не только фиктивные значения, такие как ваш x.) В некоторых случаях он не выбирает оптимальный интервал, но я думаю, что он всегда будет близок (т.е. пробелы не более чем на 1 больше, чем необходимо) и всегда возвращать правильное количество элементов.

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

В качестве примера того, как использовать его:

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) 

(это не является оптимальным, так как последняя линия имеет пункты на 2-3 и пустые места/пробелы на 0-1 и 4, в то время как ваше решение с y имеет только пробелы размера 1)

Кроме того, хотя это не соответствует вашему примеру (который будет 0, 2, 4 в индексировании на основе нуля), следующий пример удовлетворяет алгоритму, который вы определили до сих пор, так как это минимизирует размер зазора. (Разрывы 1-го размера по индексам 0 и 2 вместо ваших, у которых есть промежутки в 1 и 3). Если 0, 2, 4 действительно лучше, чем 1, 3, 4, вам нужно решить , почему именно, и добавьте это к определению вашего алгоритма.

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

На самом деле, это своего рода restricted partition проблемы. Для деления d предметов через h часов вы хотите найти перегородку h-d не более h-d частей, где max(parts) - самое маленькое, что может быть. Например. разделение 2 предметов на 5 часов: оптимальное решение - 1 + 1 + 1, потому что у него есть не более 3-х частей, и max(parts) == 1, что является лучшим, что вы можете сделать. В качестве примера без единого решения у 3 предметов за 5 часов 1 + 1, но есть разные способы его укомплектования, включая 0,2,4, 1,3,4 и 0,2,3.