Разделение списка на отдельные части длины в специальном состоянии

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

пример:

если у нас есть список [1,3,4,11,12,19,20,21] и мы решили, что его следует разделить на 3 части, его следует разделить на [1,3,4],[11,12],[19,20,21] . В том же случае, если мы решили разделить его на 4, мы получим:

  [1,3,4],[11],[12],[19,20,21]. 

Чтобы уточнить «разницу между максимальным числом в группе и всеми остальными» – [1,3,4] = 4 – 1 + 4 – 3 + 4 – 4 = 4, [11] = 11 – 11 = 0, [ 12,19] = 19 – 12 + 19 – 19 = 7, [20,21] = 21 -20 + 21 – 21 = 1. Общая разность = 12. В другом возможном случае [1,3,4] = 4 – 1 + 4 – 3 + 4 – 4 = 4, [11,12,19] = 19 – 11 + 19 – 12 + 19 – 19 = 12, [20,21] = 21 – 20 + 21 – 21 = 0 Общая разница = 16. Это расчет превышения производительности. Это связано с тем, что большое число (представляющее, например, прочность) должно заменить наименьшее число в группе (самое слабое). Использование сверхсильной части было бы слишком дорогостоящим или тяжелым, поэтому необходима оптимизация.

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

Мне было интересно, есть ли какая-нибудь функция сборки в python или Spyder или что-то подобное. Если мне нужно написать код, можете ли вы мне помочь?

Я пытаюсь работать в случайном списке, разделенном на 10, чтобы повторно применить его в разных ситуациях. l = sorted(random.sample(range(100), 10)).

3 Solutions collect form web for “Разделение списка на отдельные части длины в специальном состоянии”

Основываясь на ваших обновленных комментариях, похоже, что вы ищете алгоритм K-Means или аналогичные вещи, которые будут группировать элементы списка в отдельные группы на основе их расстояния от предлагаемых центров (это то, что действительно измеряет ваш разностный расчет) ,

В вашем критерии обратите внимание, что никогда не имеет смысла вычитать максимум каждой подгруппы из себя, так как по определению это всегда равно нулю. Итак, вы действительно смотрите на сумму максимального минус каждый элемент, по всем элементам, отличным от max (что делать с дубликатами, это также вопрос, на который вам нужно ответить). K-Means будет делать что-то другое (он будет смотреть на расстояние каждой точки от среднего значения очков), но по духу это одно и то же. Вы можете изменить k-средства, чтобы использовать свое понятие группового балла, хотя я не вижу никакой пользы от этого с точки зрения выхода из кластеризации – мне нужно будет увидеть какие-то математические доказательства предельного поведения различные критерии, чтобы убедиться, что это имеет значение.

Вы можете легко достичь этого с sklearn модулей sklearn и numpy :

 from sklearn import cluster as cluster import numpy as np km = cluster.KMeans(n_clusters=4) example_data = np.asarray([1,2,3, 11,12, 20,21,22, 30,35])[:,None] km.fit(example_data) 

Затем посмотрите на km.labels_ :

 In [65]: km.labels_ Out[65]: array([0, 0, 0, 3, 3, 1, 1, 1, 2, 2], dtype=int32) 

Вы можете видеть, что это будет объединено [1,2,3] , [11, 12] , [20, 21 , 22] , [30, 35] . Ниже приведен какой-то код, который действительно получает это для вас:

 In [74]: example_data.tolist()[0] Out[74]: [1, 2, 3, 11, 12, 20, 21, 22, 30, 35] In [75]: [[x for i,x in enumerate(example_data.tolist()[0]) if km.labels_[i] == j] for j in range(km.n_clusters)] Out[75]: [[1, 2, 3], [20, 21, 22], [30, 35], [11, 12]] 

Но обратите внимание, что это не идеально: это итеративный метод, который не гарантируется сближением с любым «истинным» решением, и для причудливых достаточных входных данных вы можете получить причудливый вывод.

Альтернативно, более общее понимание того, что вы хотите, – это выбрать целые индексы i[0] через i[k] , такие, что

 sub_lists[j] = original_list[i[j]:i[j+1]] 

с i[0]=0 и i[k+1] понимается как «все остальное в списке». Затем определите:

 sub_lens = [len(s) for s in sub_lists] max_len = max(sub_lens) criterion(k, i[0], ..., i[k]) = max(max_len - s_len for s_len in sub_lens) 

Таким образом, решение для вас – это набор параметров, (k, i[0], ..., i[k]) и вы хотите, чтобы выбор минимизировал вышеуказанный criterion выражения.

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

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

 >>> def slicer(l,n): ... le=len(l) ... S=int(np.around(float(le)/n)) ... return [l[i:i+S] for i in range(0,le,S)] ... >>> slicer([1,3,4,11,12,19,20,21],2) [[1, 3, 4, 11], [12, 19, 20, 21]] >>> slicer([1,3,4,11,12,19,20,21],3) [[1, 3, 4], [11, 12, 19], [20, 21]] >>> slicer([1,3,4,11,12,19,20,21],4) [[1, 3], [4, 11], [12, 19], [20, 21]] 

Здесь я использую numpy.around для округления float(le)/n для получения истинного среза!

Изменить: по уточненному вопросу, вот еще один алгоритм. Я все еще сохранил первоначальный ответ ниже, если это имеет значение.

Вы можете решить проблему с помощью динамического программирования. Обратите внимание, что приведенный ниже код не оптимизирован для скорости, потому что я думал, что это будет слишком сложно понять. Если вы тщательно его реализуете, вы можете сделать это в O(N * K) , где N – длина a а K – количество наборов для разбиения на.

 a = [1,3,4,11,12,19,20,21] S = [] K = 3 # memoize results in (len(a) + 1) by K array memo_partitions = [[None for j in xrange(len(a) + 1)] for i in xrange(K + 1)] def compute_cost(arr): # this is the objective to be minimized if len(arr) == 0: return 0 return sum(arr[-1] - x for x in arr) def compute_best_partition(k, n): # computes the best partition of the first `n` elements of `a` # into `k` parts if n == 0: return [[] for _ in xrange(k)], 0 if k == 1: return [a[:n]], compute_cost(a[:n]) if memo_partitions[k][n] is not None: return memo_partitions[k][n] best_partition = [[] for _ in xrange(k - 1)] + [a[:n]] best_cost = compute_cost(a[:n]) for i in xrange(1, n): last_group = a[i:n] additional_cost = compute_cost(last_group) partition, cost = compute_best_partition(k - 1, i) if cost + additional_cost < best_cost: best_partition = partition[:] best_partition.append(last_group) best_cost = cost + additional_cost memo_partitions[k][n] = (best_partition, best_cost) return memo_partitions[k][n] best_partition, cost = compute_best_partition(K, len(a)) print best_partition 

Оригинальный ответ ниже.

Вот два подхода, которые могут делать то, что вы хотите. Предположим, что ваши номера в порядке возрастания,

 a[0], a[1], ... , a[n - 1] 

Пусть max_diff(S) обозначает максимальную разность между двумя элементами множества S Мы хотим разбить числа на множества S[0], ... , S[k - 1] такие, что max_diff(S[i]) малы.

Во-первых, предположим, что мы пытаемся минимизировать сумму max_diff(S[i]) . Обратите внимание, что сумма max_diff(S[i]) – это просто a[n - 1] - a[0] минус «зазоры» между S[i] . Таким образом, вы можете просто найти k - 1 наибольший из a[i + 1] - a[i] и исключить их. В коде python,

 a = [1,3,4,11,12,19,20,21] S = [] k = 3 diffs = [(a[i + 1] - a[i], i) for i in xrange(len(a) - 1)] diffs.sort() best_cuts = [i for diff, i in diffs[-k:]] best_cuts.sort() last_cut = 0 for cut in best_cuts: S.append(a[last_cut:cut + 1]) last_cut = cut + 1 S.append(a[last_cut:]) print S 

В качестве альтернативы предположим, что мы пытаемся минимизировать максимум max_diff(S[i]) . Затем мы можем выполнить бинарный поиск по достижимой величине. В коде,

 a = [1,3,4,11,12,19,20,21] S = [] k = 3 best_partition = None low, high = 0, max(a) while low < high: mid = (low + high) / 2 # try to get all max_diffs <= mid full_partition = [] last_set = [a[0]] for val in a[1:]: if val > last_set[0] + mid: full_partition.append(last_set) last_set = [val] else: last_set.append(val) full_partition.append(last_set) if len(full_partition) > k: low = mid + 1 else: high = mid best_partition = full_partition S = best_partition print S 
Python - лучший язык программирования в мире.