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

Question

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

Короче, как то так:

A | C | E
A | D | F
B | D | F
B | D | F
  | D | 

Важным отличием от, скажем, стиля представления Windows Explorer является то, что я хочу, чтобы буквы оставались друг с другом. Не нарушая среднюю группу. Чтобы учесть это, мне все равно, если один столбец - это пара слишком высоких записей.

Я начал с сортировки массива документов по имени и разделения их на вложенный массив. Итак, я знаю (или могу легко узнать):

• Сколько уникальных букв
• Сколько букв в каждой группе
• Сколько всего записей
• Среднее среднее количество значений в каждом столбце (в идеале, но не обязательно)

Мне все равно, какие ваши ответы приходят. Я ищу алгоритм, а не реализацию, чтобы вы могли кодировать все что угодно (кроме, возможно, Fortran). объяснение в HTML тоже может быть непростым делом.

Я приглашаю кого-нибудь сойти с ума по тегам, потому что я не мог придумать ничего важного, и нет, это не домашнее задание, поэтому, пожалуйста, не отмечайте это как таковое.

Answer 1

Возможно, это поможет, если вы посмотрите на проблему следующим образом:

Для вашего примера у вас есть такая строка:

AA BB C DDDD E FFF

Космические позиции - это места, где вы можете начать новый столбец. В любом другом месте вы не должны хранить одинаковые буквы в одном столбце. Таким образом, вы можете пометить позицию в космосе так:

AA1BB2C3DDDD4E5FFF

Теперь у вас есть 5 позиций, в которых вы можете либо разбить столбец, либо нет, так как это двоичное решение, используйте для этого строку из 0 и 1 и грубую силу для каждой возможной комбинации:

12345

00000 -> no break at all, column count = 1, max. lines = 13
...
01010 -> your example, column count = 3, max. lines = 5
...
11111 -> breaks everywhere, column count = 6, max. lines = 4

Это попытка грубой силы, но вы можете легко увидеть, что число 1 влияет на количество столбцов (количество столбцов = число 1 + 1), и вы хотите минимизировать макс. линий, это должно быть возможно как-то вычислить, не проверяя каждую комбинацию.

РЕДАКТИРОВАТЬ 2: Вы не узнали, что хотите 3 столбца, это облегчает задачу, поскольку вы знаете, что у вас будет только 3 1, но это все еще грубая сила.

РЕДАКТИРОВАТЬ: Другой подход, который я бы одобрил:

Напишите, что буквы считаются так:

A B C D E F
2 2 1 4 1 3

Теперь вы можете объединять буквы рядом друг с другом. Всегда выбирайте две буквы с наименьшей суммой:

2 2 1 4 1 3 - lowest = "2 1"
2  3  4 1 3 - lowest = "1 3"
2  3  4  4  - lowest = "2 3"
  5   4  4  - stop now, as we have 3 columns now

Result: AABBC, DDDD, EFFF

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

Answer 2

Нет общего решения этой проблемы с учетом ваших ограничений, если вход не ограничен. Рассмотрим, например, коллекцию с одним документом, начинающимся с букв A, B, C, E и F, и 15 (или миллион) документов, начинающихся с D. Чтобы сгруппировать все D в один столбец, длина столбца должно быть не менее 15. Если вы используете более двух столбцов, то в лучшем случае столбец 1 будет иметь длину 3, столбец 2 будет иметь длину 15 (или миллион), а столбец 3 - длину 2. Это нарушает Ваше ограничение "в пределах нескольких записей".

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

Answer 3

Ну, вы всегда можете иметь несколько дополнительных строк в каждом столбце. Я имею в виду, что если у вас 2 А, 2 В и 33 С, то третий столбец будет довольно высоким по сравнению с другими.

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

Что вы можете сделать, это:

• Подсчитайте количество предметов.
• Посмотрите, где упадет первая треть.
• Если это именно то место, где нужно поменять букву, значит, вам повезло:)
• Если нет, то минимизируйте расстояние между точкой разделения третьей части и точкой изменения предыдущей / следующей буквы - то есть, если есть изменение буквы на 2 записи до и на 10 записей после, то перейдите к предыдущей.
• Наконец, возьмите остаток, разделите на два и следуйте той же логике, чтобы разделить как можно ближе к среднему значению.

Answer 4

Вот что вы можете попробовать. Поскольку вы знаете свой идеальный номер столбца (n), поместите все элементы в первый столбец, чтобы начать с.

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

Запуск по столбцам последовательно.

Пусть количество элементов в текущем столбце равно numCurrent.

Если numCurrent

Отслеживание элементов, которые начинаются с первой буквы (groupFirst) и последней буквы (groupLast) текущего столбца.

Рассчитать количество элементов предыдущего столбца (если оно есть) как numPrev. Если abs (n-numCurrent)> abs (n-numPrev + groupFirst), переместите groupFirst в предыдущий столбец.

Пересчитать numCurrent.

Как и раньше, если есть следующий столбец, переместите в него groupLast, если abs (n-numCurrent)> abs (n-numNext + groupLast).

Сполосните и повторите. Чем больше полосканий, тем аккуратнее это должно выглядеть. Будет точка, в которой больше не будет никаких изменений, а также точки, в которых она может просто продолжаться. Вы сами решаете, сколько итераций.

Answer 5

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

У вас есть фиксированное количество потенциальных точек разделения и определенное количество разделений. Вы должны иметь возможность иметь что-то вроде

(splits, max_ht, min_ht) = split_list(list, requested_splits, 
                                      curr_max, curr_min)

Функция должна перебирать потенциальные точки разделения и рекурсивно вызывать себя (с одним меньшим запрошенным разделением) в оставшейся части списка. Например.,

def split_list(list, requested_splits, curr_max, curr_min):
    best_splits = []
    best_split_len = curr_max-curr_min
    best_max = curr_max
    best_min = curr_min

    if requested_splits == 0:
        return (best_splits, curr_max, curr_min)
    for candidate in candidate_split_points:
        this_max = max(curr_max, len(<list up to split point>)
        this_min = min(curr_min, len(<list up to split point>)
        (splits, new_max, new_min) = split_list(<list after split point>,
                                                requested_splits-1,
                                                this_max, this_min)
        if (new_max-new_min) < best_split_len:
            best_split_len = new_max - new_min
            best_max = new_max
            best_min = new_min
            best_splits = [candidate] + splits
    return (best_splits, best_max, best_min)

Answer 6

Во-первых, передайте документы, чтобы создать массив кортежей letter-> count.

Первая запись (первая буква в массиве) -> документ 0

Затем найдите записи, которые должны появиться во втором и третьем столбцах, пройдясь по массиву, добавив счетчики, но остановившись непосредственно перед тем, как вы пройдете порог для 2-го и 3-го столбцов (который является 1/3 и 2 / 3 от общего количества).

Answer 7

Я думаю, вы должны начать с определения своего рода «меры», которая скажет вам, какой макет является лучшим, например, возьмите сумму (average_size - actual_size (column)) ^ 2 для всех столбцов. Тогда, поскольку у вас всегда есть 3 столбца (это правильно?), Должно быть достаточно быстро взять все возможные деления и найти тот, который максимизирует вашу меру.