Хороший алгоритм для объединения объектов от N перечисляет в один со сбалансированным распределением?

Во-первых, этот ответ является большим количеством хода мыслей, чем concete решение.

Хорошо, таким образом, у Вас есть список 3 объектов (A1, A2, A3), где Вы хотите, чтобы A1 был где-нибудь в первом 1/3 целевого списка, A2 во втором 1/3 целевого списка и A3 в третьем 1/3. Аналогично Вы хотите, чтобы B1 был в первом 1/2 и т.д...

Таким образом, Вы выделяете свой список 10 как массив, затем запустите со списка с большинством объектов, в этом случае C. Вычислите пятно, где C1 должен упасть (1.5) Отбрасывание C1 в самом близком месте, (в этом случае, или 1 или 2), затем вычислить, где C2 должен упасть (3.5) и продолжить процесс, пока больше нет Cs.

Затем пойдите со списком с second-most количеством объектов. В этом случае, A. Вычислите, куда A1 идет (1.66), так попробуйте 2 сначала. Если Вы уже помещаете C1 там, попробуйте 1. Сделайте то же для A2 (4.66) и A3 (7.66). Наконец, мы действительно перечисляем B. B1 должен пойти в 2,5, так попробуйте 2 или 3. Если и взяты, попробуйте 1 и 4 и продолжайте движение радиально, пока Вы не находите пустое место. Сделайте то же для B2.

Вы закончите с чем-то вроде этого при выборе более низкого количества:

C1 A1 C2 A2 C3 B1 C4 A3 C5 B2

или это, если Вы выбираете верхнее число:

A1 C1 B1 C2 A2 C3 A3 C4 B2 C5

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

• Сделайте хеш-таблицу списков.
• Для каждого списка сохраните энный элемент в списке под ключом (/ n (+ (length list) 1))
• Дополнительно, переставьте списки под каждым ключом в хеш-таблице или отсортируйте их в некотором роде
• Свяжите списки в хеше отсортированным ключом

Я думаю о делении и завоевываю подход. Каждое повторение которого Вы разделяете все списки с элементами> 1 в половине и рекурсивно вызываете. Когда Вы добираетесь до точки, где все списки кроме каждый имеет один элемент, можно случайным образом объединить их, всплывающее окно уровень и случайным образом объединить списки, удаленные из того кадра, где длина была той... и так далее.

Что-то как следующее - то, что я думаю:

- filter lists into three categories
    - lists of length 1
    - first half of the elements of lists with > 1 elements
    - second half of the elements of lists with > 1 elements
- recurse on the first and second half of the lists if they have > 1 element
    - combine results of above computation in order
- randomly combine the list of singletons into returned list 

Вы могли просто объединить три списка в единственный список и затем UNSORT тот список. Неотсортированный список должен достигнуть Вашего требования 'равномерно распределенных' без слишком большого усилия.

Вот реализация невида: http://www.vanheusden.com/unsort/.

Быстрое предложение, в псевдокоде выхода Python:

merge = list()
lists = list(list_a, list_b, list_c)
lists.sort_by(length, descending)

while lists is not empty:
    l = lists.remove_first()
    merge.append(l.remove_first())
    if l is not empty:
        next = lists.remove_first()
        lists.append(l)
        lists.sort_by(length, descending)
        lists.prepend(next)

Это должно распределить элементы из более коротких списков более равномерно, чем другие предложения здесь.