Следующая программа представляет собой недорогую эвристику. Он распределяет значения по «корзинам», помещая большие значения вместе с маленькими, выбирая значения с одного конца отсортированного списка в одном раунде, а с другого - в следующем. Распределение в циклическом цикле гарантирует соблюдение правил о количестве элементов в каждой группе. Это эвристический алгоритм, а не алгоритм, потому что он дает хорошие решения, но без гарантии, что лучшие не существует.
Теоретически, если имеется достаточно значений, и они распределены равномерно или нормально, то есть вероятность, что просто случайное размещение значений в сегментах приведет к одинаковым средствам для блоков. Предполагая, что набор данных мал, эта эвристика повышает шансы на хорошее решение. Зная больше о размере и статистическом распределении наборов данных, можно было бы разработать лучшую эвристику или алгоритм.
from random import randint, seed
from itertools import cycle,chain
def chunks(q, n):
q = list(q)
for i in range(0, len(q), n):
yield q[i:i+n]
def shuffle(q, n):
q = list(q)
m = len(q)//2
left = list(chunks(q[:m],n))
right = list(chunks(reversed(q[m:]),n)) + [[]]
return chain(*(a+b for a,b in zip(left, right)))
def listarray(n):
return [list() for _ in range(n)]
def mean(q):
return sum(q)/len(q)
def report(q):
for x in q:
print mean(x), len(x), x
SIZE = 5
COUNT= 37
#seed(SIZE)
data = [randint(1,1000) for _ in range(COUNT)]
data = sorted(data)
NBUCKETS = (COUNT+SIZE-1) // SIZE
order = shuffle(range(COUNT), NBUCKETS)
posts = cycle(range(NBUCKETS))
buckets = listarray(NBUCKETS)
for o in order:
i = posts.next()
buckets[i].append(data[o])
report(buckets)
print mean(data)
Сложность является логарифмической из-за шага сортировки. Вот примеры результатов:
439 5 [15, 988, 238, 624, 332]
447 5 [58, 961, 269, 616, 335]
467 5 [60, 894, 276, 613, 495]
442 5 [83, 857, 278, 570, 425]
422 5 [95, 821, 287, 560, 347]
442 4 [133, 802, 294, 542]
440 4 [170, 766, 301, 524]
418 4 [184, 652, 326, 512]
440
Обратите внимание, что преобладает требование к размеру сегментов, что означает, что средства не будут близки, если разница в исходных данных велика. Вы можете попробовать с этим набором данных:
data = sorted(data) + [100000]
Ведро, содержащее 100000, получит как минимум еще 3 датума.
Я придумал эту эвристическую мысль о том, что группа детей будет делать, если передаст пачку банкнот разного достоинства и попросит их поделиться согласно правилам этой игры. Это статистически обоснованно, и O (log (N)).