根据集合最大长度缩短列表数量，将多余的移动到新列表中

Question

我有N个不同长度的列表。这些列表包含要在UI中显示的项，并且我的最大UI预算为X。任何多余的项都将转到下拉菜单中。我需要做的是将列表中的项移动到它们的“溢出”等效项中，以便所有列表的总长度等于或小于最大长度。我想确保没有一张单子的长度比必要的短，而且它们的长度尽可能接近相等。示例：

我有三个列表，l1=range(10)，l2=range(15)和{}和{}。我需要得到的是l1和{}保持原样，l3缩短为15个条目，因为10+15+15=45。如果l1=range(15)取而代之的是，我应该得到两个包含13项的列表和一个包含14项的列表。在

目前，我有一个函数，它使用while循环来完成此操作，如下所示：

def shortenLists(maxLength, *input_lists):
    overflows = [[] for n in input_lists]

    while sum(len(l) for l in input_lists) > maxLength:
        longestList = max(input_lists, key=len)
        index = input_lists.index(longestList)
        overflows[index].append(longestList.pop())

    [o.reverse() for o in overflows]
    return input_lists, overflows

这基本上看起来是可行的，但我不特别喜欢使用while循环来处理这样的事情；只需计算出要从每个列表中删除多少项应该相对简单一些。此方法还依赖于使用列表.索引在最长的一个索引中查找一个索引项的最长的一个索引项的排序。在

该函数返回一个由两个列表组成的元组，其中裁剪的输入列表按顺序排列，溢出缓冲区的顺序相同。我不确定这是否是最好的方法，最好将它们压缩，这样它就会返回（（list，overflow），（list，overflow））。在

Answer 1

您的代码稍有变化：

def shortenLists(maxLength, *input_lists):
    item_per_list = maxLength / len(input_lists)
    overflows = []
    for (i, l) in enumerate(input_lists):
        overflows.append(l[item_per_list:])
        l[item_per_list:] = []
    return input_lists, overflows

Answer 2

我认为就我的目的而言，解决方案是实际使用while循环。我扩展了我的代码，只需先对列表进行切片，这样列表就不会超过maxLength，如下所示：

for index, l in enumerate(new_lists):
    overflows[index] = new_lists[index][maxLength:]
    new_lists[index] = new_lists[index][:maxLength]

我有一个关于切片的后续问题，不过。。。有没有可能在适当的地方切？我注意到当我这样做的时候：

^{pr2}$

它实际上会创建所有内容的新副本，这显然对我的目的不太管用。因此使用索引。不管怎样，回到主题。。。在

当首先循环所有列表一次并确保它们都不超过最大长度时，钳制50个10**5项的列表的执行时间从大约90秒增加到0.2秒。就我而言，这已经足够了；我可能永远不会有超过几百个项目的列表，通常也不会超过十几个列表。因此，对于需要操作的数据量，我的执行时间实际上只有几厘米。在

如果有人为了代码的美好而对如何摆脱讨厌的while loop业务有任何进一步的建议，那将不胜感激，但目前我认为问题基本上得到了回答。如果有人感兴趣，代码如下：

def shortenLists(maxLength, *input_lists):
    #create copies of all input lists
    new_lists = [list(l) for l in input_lists]
    #create overflow lists
    overflows = [[] for n in input_lists]

    #make sure no list is longer than maxLength
    for index, l in enumerate(new_lists):
        overflows[index] = new_lists[index][maxLength:]
        new_lists[index] = new_lists[index][:maxLength]
        overflows[index].reverse()

    #loop until the total length is less or equal than maxLength
    while sum(len(l) for l in new_lists) > maxLength:
        #longest list's index
        index = max(enumerate(new_lists), key = lambda tup: len(tup[1]))[0]
        #move last item from new_lists[index] to overflow[index],
        #shortening it by 1
        overflows[index].append(new_lists[index].pop())

    #reverse all overflow lists, because "pop" is added from the back
    [o.reverse() for o in overflows]
    return zip(new_lists, overflows)

Answer 3

我认为最好是从最短的列表开始，而不是从最长的列表开始。在这种情况下，任何短于每个列表的平均和理想项目数的列表都可以完全复制，剩余的空间将重新计算并重新分配到其他列表中。在

def shortenLists(maxLength, *input_lists):
    overflows = [[] for n in input_lists]
    result_lists = [[] for n in input_lists]

    for i in xrange(len(input_lists)):
        remaining = [l for idx, l in enumerate(input_lists) if not len(result_lists[idx])]
        shortestList = min(remaining, key=len)
        idxSL = input_lists.index(shortestList)
        numElems = int(math.floor(maxLength/len(remaining)))
        toCopy = min(numElems, len(shortestList))
        result_lists[idxSL] = shortestList[:toCopy]
        if numElems < len(shortestList):
            overflows[idxSL] = shortestList[numElems:]
        maxLength -= toCopy