Разбиение списка K-длины на L подсписков, которые настолько «четны», насколько это возможно, даже если K / L оставляет остаток

Question

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

Допустим, у меня есть список из 17 элементов.Для краткости представим этот список как ABCDEFGHIJKLMNOPQ.Если бы я хотел разделить это на 7 достаточно «четных» подсписков, это могло бы выглядеть так:

ABC DE FGH IJ KL MNO PQ

Здесь длины каждого подсписка составляют 3, 2, 3, 2, 2, 3, 2 .Максимальная длина только на одну единицу больше минимальной: ABC DE FGH I JKL MN OPQ также имеет семь подсписков, но диапазон длин здесь равен двум.

Кроме того, проверьте, сколько 2 отделяют каждую пару из 3: это соответствует тому же правилу RANGE ≤ 1. Диапазон длин в ABC DEF GH IJ KLM NO PQ также равно 1, но они несбалансированы: 3, 3, 2, 2, 3, 2, 2. В идеале, если бы мы продолжали сокращать подсписок таким образом, числа никогда не отклонялись быдруг от друга более чем на один.

Конечно, существует более одного способа «равномерного» разделения списка на подсписки таким способом.Я не ищу исчерпывающий набор решений - если я могу получить одно решение в Python для списка любой длины и любого количества подсписков, для меня этого достаточно.Проблема в том, что я даже не знаю, с чего начать при решении такой проблемы.Кто-нибудь знает, что я ищу?

Answer 1

>>> s='ABCDEFGHIJKLMNOPQ'
>>> parts=7
>>> [s[i*len(s)//parts:(i+1)*len(s)//parts] for i in range(parts)]
['AB', 'CD', 'EFG', 'HI', 'JKL', 'MN', 'OPQ']


>>> import string
>>> for j in range(26):
...  print [string.uppercase[i*j//parts:(i+1)*j//parts] for i in range(parts)]
... 
['', '', '', '', '', '', '']
['', '', '', '', '', '', 'A']
['', '', '', 'A', '', '', 'B']
['', '', 'A', '', 'B', '', 'C']
['', 'A', '', 'B', '', 'C', 'D']
['', 'A', 'B', '', 'C', 'D', 'E']
['', 'A', 'B', 'C', 'D', 'E', 'F']
['A', 'B', 'C', 'D', 'E', 'F', 'G']
['A', 'B', 'C', 'D', 'E', 'F', 'GH']
['A', 'B', 'C', 'DE', 'F', 'G', 'HI']
['A', 'B', 'CD', 'E', 'FG', 'H', 'IJ']
['A', 'BC', 'D', 'EF', 'G', 'HI', 'JK']
['A', 'BC', 'DE', 'F', 'GH', 'IJ', 'KL']
['A', 'BC', 'DE', 'FG', 'HI', 'JK', 'LM']
['AB', 'CD', 'EF', 'GH', 'IJ', 'KL', 'MN']
['AB', 'CD', 'EF', 'GH', 'IJ', 'KL', 'MNO']
['AB', 'CD', 'EF', 'GHI', 'JK', 'LM', 'NOP']
['AB', 'CD', 'EFG', 'HI', 'JKL', 'MN', 'OPQ']
['AB', 'CDE', 'FG', 'HIJ', 'KL', 'MNO', 'PQR']
['AB', 'CDE', 'FGH', 'IJ', 'KLM', 'NOP', 'QRS']
['AB', 'CDE', 'FGH', 'IJK', 'LMN', 'OPQ', 'RST']
['ABC', 'DEF', 'GHI', 'JKL', 'MNO', 'PQR', 'STU']
['ABC', 'DEF', 'GHI', 'JKL', 'MNO', 'PQR', 'STUV']
['ABC', 'DEF', 'GHI', 'JKLM', 'NOP', 'QRS', 'TUVW']
['ABC', 'DEF', 'GHIJ', 'KLM', 'NOPQ', 'RST', 'UVWX']
['ABC', 'DEFG', 'HIJ', 'KLMN', 'OPQ', 'RSTU', 'VWXY']

Answer 2

Если у вас есть список длины N, и вы хотите некоторое количество подсписков S, мне кажется, что вы должны начать с деления с остатком.Для N == 17 и S == 7 у вас есть 17 // 7 == 2 и 17% 7 == 3. Таким образом, вы можете начать с 7 значений длины, равных 2, но знайте, что вам нужно увеличить 3 длинызначения на 1 для обработки остатка.Поскольку ваш список значений длины имеет длину 7, и у вас есть 3 значения для приращения, вы можете вычислить X = 7/3 и использовать это как шаг: увеличить 0-й элемент, затем элемент int (X), int (2)* X) и т. Д.

Если это не сработает для вас, я предлагаю вам взять книгу под названием Руководство по разработке алгоритмов от Skiena, и просмотреть набор идревовидные алгоритмы.

http://www.algorist.com/

Answer 3

См. Пример "grouper" в http://docs.python.org/library/itertools.html