Разделить отсортированный список с учетом ограничений

Question

Вот вопрос:

Учитывая отсортированный список, скажем, целых чисел (вы можете предположить, что они положительны, если это упрощает задачу), разбейте список на 'n'равные по размеру разделы (или настолько равные, насколько это возможно), при условии ограничения, что ни одно из целых чисел не появляется более чем в одном таком разделе.

Ограничение по сути означает, что если у вас есть список {1,1,2, 2}

тогда все они должны быть в одном наборе, и все 2 должны быть в одном наборе.Все 1 и 2 также могут быть в одном наборе.Но у нас не может быть одного из 1 в первом разделе и второго 1 во втором разделе.

Пример 1: </p> <pre><code> List: {1,1,2,2,3,3,4,4} Number of partitions to make: 4 Answer: {1,1} {2,2} {3,3} {4,4}

Пример2: (хитрее)

List: {1,1,2,2,2,3,3,4,4,4,4,4,4,4,4} 

Number of partitions to make : 3

Answer: {1,1,2,2} {3,3} {4,4,4,4,4,4,4,4}

    OR: {1,1} {2,2,3,3} {4,4,4,4,4,4,4,4}
</code>

Обратите внимание здесь, что третий раздел должен иметь размер 8, потому что из-за ограничения все 4 должны быть втот же раздел.

Может быть множество других сложных случаев.Дайте мне знать, если кому-то понадобится больше примеров.

Итак, вопрос в том, как лучше всего подойти или решить эту проблему?

Answer 1

Самое простое решение, которое я могу придумать, это:

1. Сначала найдите все те же элементы в списке (используйте что-то вроде хеширования, чтобы найти их или подсчитать сортировку, если вы знаете диапазон перед рукой).), а также сохранить их размер.

2. Теперь у вас будут наборы повторяющихся чисел (например, {1,1} {2,2}).После этого шага попробуйте найти количество списков, которые у вас есть, и сгруппируйте их, чтобы сформировать n разделов (как указано в описании проблемы).НапримерВ последнем хитром примере у нас будет 4 списка в конце, вам нужно 3 раздела.Вы можете найти 2 небольших списка и объединить их в форму 1, повторяйте это, пока не достигнете необходимого количества разделов.

Answer 2

Это хитрая версия проблемы k-раздела или проблемы упаковки бинов . Если вы посчитаете количество вхождений каждого элемента и поместите их в мультимножество, то вы в основном пытаетесь разделить эти числа на наборы с одинаковой суммой.
Если n = 2, для него есть несколько псевдополиномиальных алгоритмов. В противном случае нет известных псевдополиномиальных алгоритмов. (и не может быть, если P = NP)
Что касается того, как подойти к нему. Если вам нужно выбрать n, просто установите его в 1 и разбейте список на себя. Если вы этого не сделаете, но у вас есть небольшие списки, просто внедрите решение грубой силы. Если вы не выбрали n и у вас длинные списки, изучите алгоритмы жадности / аппроксимации и постарайтесь точно определить, что вы подразумеваете под «как можно более равным». (Вы имеете в виду максимальную разницу? Дисперсия? Что-то еще?)
Удачи.