在特殊情况下将列表拆分为不同长度部分

Question

我需要一个算法将不同的制造部件分成不均匀的组。主要的条件是组内最大人数与其他所有人数之间的差距应尽可能小。为

示例：

如果我们有列表[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)).

Answer 1

根据您更新的评论，听起来您正在寻找K-Means算法，或类似的东西，它将根据列表元素与建议的中心的距离将列表元素分为不同的组（这是您的差异计算真正衡量的）。在

在您的标准中，请注意，从自身减去每个子组的最大值是没有意义的，因为根据定义，这个值总是零。所以，实际上，你看到的是max减去每个元素的和，超过所有非max元素（如何处理重复项也是一个需要回答的问题）。K-Means会做一些不同的事情（它会观察每个点与平均点的距离），但在精神上它是一样的。你可以修改k-means来使用你的组分数的概念，尽管在聚类输出方面我并没有看到任何好处，我需要看到一些关于不同标准的限制行为的数学证明，以确信它是重要的。在

使用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_：

^{pr2}$

您可以看到这将组合在一起[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]到{}，这样

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。在

这个问题的一般解决方案相当复杂。但是如果您愿意接受一个贪婪的解决方案，除了最后的子列表之外，它将非常平衡，许多{a1}都可以。在

Answer 2

由于您没有提到切片背后的逻辑，我建议您使用以下函数：

>>> 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]]

在这里，我使用^{}取整float(le)/n以获得真正的切片！在

Answer 3

编辑：基于澄清的问题，这里有另一种算法。我仍然保留了下面的原始回复，以防相关。

你可以用动态规划来解决这个问题。请注意，下面的代码没有针对速度进行优化，因为我认为这会使它太难理解。如果您仔细地实现它，您可以在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

以下是原始回复。

这里有两种方法可以满足您的需要。假设你的数字按升序排列

^{pr2}$

让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