Разбиение списка K-длины на L подсписков, которые настолько "четны", насколько это возможно, даже если K/L оставляет остаток
Я не знаю лучшего способа сказать, что я ищу, поэтому, пожалуйста, потерпите меня.
Допустим, у меня есть список из 17 элементов. Для краткости представим этот список как ABCDEFGHIJKLMNOPQ, Если бы я хотел разделить это на 7 достаточно "четных" подсписков, это могло бы выглядеть так:
ABCDEFGHIJKLMNOPQ
Здесь длины каждого подсписка составляют 3, 2, 3, 2, 2, 3, 2. Максимальная длина всего на один больше минимальной длины: ABCDEFGHIJKLMNOPQ также имеет семь подсписков, но диапазон длин здесь равен двум.
Кроме того, проверьте, сколько 2 отделяют каждую пару из 3: это следует тому же правилу RANGE ≤ 1. Диапазон длин в ABCDEFGHIJKLMNOPQ равно 1, но они несбалансированы: 3, 3, 2, 2, 3, 2, 2. В идеале, если бы мы продолжали сокращать подсписок таким образом, числа никогда не отклонялись бы друг от друга на больше одного.
Конечно, существует несколько способов "равномерно" разделить список на подсписки таким способом. Я не ищу исчерпывающий набор решений - если я могу получить одно решение в Python для списка любой длины и любого количества подсписков, для меня этого вполне достаточно. Проблема в том, что я даже не знаю, с чего начать при решении такой проблемы. Кто-нибудь знает, что я ищу?
3 ответа
Если у вас есть список длины 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). * Х) пункт и тд.
Если это не работает для вас, я предлагаю вам взять книгу под названием "Руководство по разработке алгоритмов" от Skiena и просмотреть алгоритмы множеств и деревьев.
>>> 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']
Смотрите пример "grouper" на http://docs.python.org/library/itertools.html