#python
Вопрос:
У меня есть список предложений, которые я зачитал в статье, и я хочу сгруппировать их в блоки одинакового размера (как можно большего), состоящие максимум из N символов, с дополнительным усложнением, заключающимся в том, чтобы блоки были примерно одинакового размера, а предложения не были разделены.
Я использую python, и наивный подход, который я имею в виду, состоит в том, чтобы:
- Повторите предложения и заполните каждое ведро, пока оно не заполнится.
- Пройдите по ведрам итеративно и попробуйте выровнять их.
Вторая часть-это то, что, я боюсь, не будет таким простым, и мне интересно, есть ли быстрый/умный способ достичь этого?
Полные данные примера были бы здесь слишком большими, но в более простой форме: [[Предложение 1 с 30 словами], [Предложение 1 с 3 словами][[Предложение 1 с 15 словами][[Предложение 1 с 10 словами], …]
Ведро будет [отправлено 1, отправлено 2…] общей длиной символов, равной сумме предложений.
И я хотел бы сгруппировать в X ведер, чтобы общая длина предложений в каждом ведре была как можно более равномерно распределена и не должна превышать определенного порога.
Комментарии:
1. Пожалуйста, приведите пример ввода/вывода.
2. достань веревку, Лен … найдите коэффициенты строки len .. тогда вам решать , сколько ведер вы хотите, если вы хотите больше ведер, затем разделите мой минимальный коэффициент, если вы хотите меньше ведер, разделите его на максимальный коэффициент.
3. Думаю, это лучший термин. Я буду обновлять.
4. @rubmz, пожалуйста, добавьте пример
5. Добавлен (что-то вроде) пример.
Ответ №1:
На первом шаге вы сгруппируете предложения в нижние группы (слева), чтобы на втором шаге можно было выполнить оптимизацию, сдвинув предложения вправо.
Имейте в виду, что будет очень большое количество перестановок этих сдвигов предложений (которые будут расти экспоненциально с увеличением числа предложений).
Простой способ реализовать это — обработать список длин предложений вместо самих предложений. Вы можете сгруппировать фактические предложения на основе группировок по длине, когда закончите.
Данные Испытаний:
sentences="""Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.""".split(". ")
sentences *=60 # 240 sentences
from random import shuffle
shuffle(sentences)
Группировка по длине предложения
SL = [len(s) for s in sentences]
bucketCount = 10
bucketSize = max(max(SL),sum(SL)//(bucketCount-1)) # safe max bucket size
groups = []
for size in SL:
if not groups or sum(groups[-1]) size>bucketSize:
groups.append([size])
else:
groups[-1].append(size)
print(*groups,sep="n")
[101, 122, 110, 106, 122, 101, 110, 101, 110, 101, 106, 101, 101, 106, 101, 110, 122, 106, 106, 101, 122, 122, 122, 110, 122, 110]
[110, 106, 110, 110, 101, 106, 122, 110, 106, 101, 101, 122, 106, 122, 122, 110, 122, 106, 122, 122, 106, 106, 122, 101, 122, 122]
[106, 122, 122, 101, 101, 110, 106, 110, 110, 101, 110, 110, 106, 106, 106, 106, 101, 122, 101, 110, 122, 122, 110, 110, 101, 122]
[106, 122, 101, 110, 106, 110, 122, 122, 110, 101, 122, 101, 110, 110, 122, 122, 106, 110, 101, 122, 101, 106, 106, 101, 101, 101]
[106, 110, 122, 101, 122, 110, 122, 122, 122, 110, 106, 101, 106, 106, 110, 106, 122, 106, 110, 106, 110, 101, 110, 110, 122, 122]
[110, 101, 110, 106, 101, 101, 110, 101, 110, 122, 122, 101, 106, 110, 110, 122, 110, 110, 122, 106, 110, 122, 106, 101, 101, 110]
[101, 101, 101, 106, 101, 106, 106, 101, 101, 122, 101, 122, 106, 122, 106, 110, 101, 122, 101, 110, 106, 106, 122, 122, 106, 106, 106]
[110, 101, 106, 106, 101, 101, 122, 106, 101, 122, 106, 101, 122, 110, 106, 106, 110, 122, 110, 110, 101, 101, 106, 110, 110, 106, 101]
[122, 101, 110, 122, 106, 122, 110, 101, 110, 101, 110, 122, 106, 106, 122, 106, 122, 110, 101, 101, 106, 106, 106, 101, 110, 110]
[122, 101, 110, 106]
Как вы можете видеть, у последней группы есть много возможностей для перехода в
Групповая оптимизация
Вот функция оптимизации «грубой силы», которая исследует перестановки сдвигов членов группы (вправо) и возвращает оптимальную группировку.
Обратите внимание, что производительность этой функции имеет много возможностей для улучшения, я не пытался оптимизировать функцию оптимизации.
# Recursive function that goes through shifting permutations
def optimize(groups,bucketSize):
if len(groups)==1: return groups
optimal = groups
minSum = min(map(sum,groups))
for i in reversed(range(1,len(groups))):
if groups[i-1][-1] sum(groups[i])<=bucketSize:
oGroups = [g.copy() for g in groups]
oGroups[i].insert(0,oGroups[i-1].pop(-1))
oGroups[:i 1] = optimize(oGroups[:i 1],bucketSize)
ms = min(map(sum,oGroups))
if ms>minSum:
minSum,optimal = ms,oGroups
return optimal
optimal = optimize(groups,bucketSize) # takes about a minute for 240 sentences
bucketSize = max(map(sum,optimal)) # Effective bucket size
for g in optimal:
print(sum(g),sum(g)-bucketSize,g)
2620 -80 [101, 122, 110, 106, 122, 101, 110, 101, 110, 101, 106, 101, 101, 106, 101, 110, 122, 106, 106, 101, 122, 122, 122, 110]
2681 -19 [122, 110, 110, 106, 110, 110, 101, 106, 122, 110, 106, 101, 101, 122, 106, 122, 122, 110, 122, 106, 122, 122, 106, 106]
2634 -66 [122, 101, 122, 122, 106, 122, 122, 101, 101, 110, 106, 110, 110, 101, 110, 110, 106, 106, 106, 106, 101, 122, 101, 110]
2700 0 [122, 122, 110, 110, 101, 122, 106, 122, 101, 110, 106, 110, 122, 122, 110, 101, 122, 101, 110, 110, 122, 122, 106, 110]
2621 -79 [101, 122, 101, 106, 106, 101, 101, 101, 106, 110, 122, 101, 122, 110, 122, 122, 122, 110, 106, 101, 106, 106, 110, 106]
2630 -70 [122, 106, 110, 106, 110, 101, 110, 110, 122, 122, 110, 101, 110, 106, 101, 101, 110, 101, 110, 122, 122, 101, 106, 110]
2599 -101 [110, 122, 110, 110, 122, 106, 110, 122, 106, 101, 101, 110, 101, 101, 101, 106, 101, 106, 106, 101, 101, 122, 101, 122]
2606 -94 [106, 122, 106, 110, 101, 122, 101, 110, 106, 106, 122, 122, 106, 106, 106, 110, 101, 106, 106, 101, 101, 122, 106, 101]
2643 -57 [122, 106, 101, 122, 110, 106, 106, 110, 122, 110, 110, 101, 101, 106, 110, 110, 106, 101, 122, 101, 110, 122, 106, 122]
2606 -94 [110, 101, 110, 101, 110, 122, 106, 106, 122, 106, 122, 110, 101, 101, 106, 106, 106, 101, 110, 110, 122, 101, 110, 106]
Эффективный размер ведра составляет 2700, а наибольшая разница в общей длине предложения составляет 101 символ (3,7%).
группировка фактических предложений
iSentence = iter(sentences)
sentenceGroups = [[next(iSentence) for _ in g] for g in optimal]
[ПРАВИТЬ]
Я нашел гораздо более быстрый способ выполнения группировок, рекурсивно найдя лучшее разделение на две части. Это не всегда так идеально оптимально, но работает намного быстрее.
def makeGroups(SL,buckets):
if buckets == 1: return [SL]
left = buckets//2 # left side buckets
lSum = sum(SL)*left/buckets # target sum for left side
mid = min(range(len(SL)),key=lambda i:abs(sum(SL[:i])-lSum))
return makeGroups(SL[:mid],left) makeGroups(SL[mid:],buckets-left)
def groupSentences(sentences,buckets):
iS = iter(sentences)
return [ [next(iS) for _ in g] for g in makeGroups([*map(len,sentences)]) ]
Это дает почти мгновенные результаты для 10 000 предложений (по сравнению с моими первоначальными решениями, которые могли занять минуты всего для 240 предложений).
Комментарии:
1. Речь идет о том, как я, наконец, решил эту проблему. Действительно, использовалась длина предложения я сгруппировал по максимальному размеру на ведро, затем повторил ведра от конца до начала и сравнил размеры ведер, таким образом, за один проход я достиг цели без особых проблем.
Ответ №2:
Итак, предположим, вам нужно поместить большое количество предметов (скажем, 327 предметов) в максимальный размер ведра (скажем, 12 предметов на ведро), верно? Вы хотите, чтобы каждый размер ведра был одинаковой длины после заполнения, но длина ведра не превышала максимального размера ведра
Получите наибольший общий знаменатель максимального размера ведра и количества предметов: тогда это то, сколько предметов вы можете поместить в каждое ведро:
from math import gcd
from random import shuffle
no_items = 327
max_bucket_size = 12
items_per_bucket = gcd(len(items), max_bucket_size)
list(range(327))
shuffle(items)
print(list((zip(*[iter(items)]*items_per_bucket))))
[(38, 273, 165),
(212, 259, 197),
(4, 181, 43),
(162, 137, 23),
(42, 146, 315),
(99, 240, 292),
(96, 182, 89),
(102, 164, 73),
(153, 248, 5),
(84, 48, 81),
(148, 214, 321),
(130, 44, 40),
(210, 312, 202),
(127, 126, 31),
(83, 9, 7),
(284, 57, 194),
(303, 109, 95),
(223, 238, 227),
(104, 10, 94),
(78, 155, 224),
(125, 271, 279),
(123, 189, 135),
(249, 290, 243),
(141, 139, 119),
(59, 311, 299),
(186, 289, 306),
(174, 241, 278),
(75, 11, 286),
(62, 228, 250),
(169, 16, 314),
(281, 63, 263),
(265, 132, 108),
(287, 129, 138),
(177, 103, 142),
(22, 230, 173),
(203, 319, 239),
(72, 180, 64),
(47, 205, 0),
(178, 255, 234),
(274, 71, 117),
(305, 316, 6),
(301, 80, 118),
(200, 86, 45),
(163, 258, 147),
(27, 232, 209),
(183, 17, 157),
(56, 302, 121),
(156, 225, 3),
(26, 282, 2),
(150, 300, 53),
(76, 207, 215),
(152, 206, 74),
(198, 28, 247),
(51, 87, 12),
(98, 19, 20),
(172, 116, 298),
(270, 195, 41),
(188, 18, 256),
(233, 226, 187),
(134, 262, 309),
(179, 190, 237),
(317, 113, 69),
(313, 34, 199),
(35, 253, 159),
(269, 308, 213),
(295, 168, 285),
(176, 54, 46),
(242, 140, 100),
(288, 191, 244),
(219, 280, 193),
(260, 307, 235),
(320, 196, 264),
(115, 277, 60),
(33, 110, 158),
(55, 24, 166),
(236, 204, 293),
(88, 120, 101),
(32, 322, 149),
(296, 97, 68),
(79, 52, 14),
(15, 29, 222),
(58, 8, 201),
(128, 272, 275),
(112, 208, 283),
(246, 220, 254),
(111, 325, 324),
(114, 304, 124),
(131, 92, 39),
(21, 1, 67),
(323, 184, 245),
(160, 171, 151),
(77, 192, 268),
(266, 136, 133),
(291, 65, 30),
(252, 276, 37),
(49, 70, 50),
(267, 13, 217),
(170, 82, 211),
(221, 216, 144),
(310, 93, 25),
(326, 106, 218),
(318, 66, 294),
(167, 154, 36),
(185, 161, 107),
(143, 145, 261),
(61, 231, 297),
(85, 257, 229),
(175, 105, 90),
(122, 251, 91)]
>
Комментарии:
1. Не так просто, поскольку предложения имеют разную длину и не должны быть разделены.
2. Я дал ответ, основанный на информации, предоставленной ОП. Я имею в виду, что это решение, просто надеясь, что это то, чего они хотят.
3. @rubmz. сделай это, братан : достань веревочку, лен … найдите коэффициенты строки len .. тогда вам решать , сколько ведер вы хотите, если вы хотите больше ведер, затем разделите мой минимальный коэффициент, если вы хотите меньше ведер, разделите его на максимальный коэффициент. и, пожалуйста, добавьте пример
4. @rubmz Итак, вы хотите, чтобы каждый размер ведра был одинаковой длины после заполнения, но длина не превышала максимальный размер ведра?
5. да @jab .. Я думаю, ооочень .. нет четкого опыта. учитывая, что он не хочет делиться примером, мы можем предположить, что в настоящее время даже размер ведра