Shorten a number of lists based on a collective max length, moving excess to new lists

Question

I have N lists of varying lengths. These lists contain items to display in a UI, and I have have a maximum UI budget of X. Any excess items go into a dropdown menu instead. What I need to do is move items from the lists into their "overflow" equivalent so that the total length of all the lists is equal or less than the max length. I want to make sure that no list is shortened less than what's necessary, and that they end up as close to equal length as possible. Example:

I have three lists, l1=range(10), l2=range(15) and l3=range(20) and maxLength=40. What I need to get from this is l1 and l2 left as-is and l3 shortened to 15 items, since 10+15+15=45. If l1=range(15) instead, I should end up with two lists with 13 items and one with 14.

At the moment, I have a function that uses a while loop to accomplish this, like so:

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

This does basically seem to work, but I don't particularly like using a while loop for something like this; it seems it ought to be relatively simple to just figure out how many items to remove from each list. This method also relies on using the list.index() method to find the index of the longest list in the input in order to add the items to the right overflow buffer, which seems like a bit of a hack.

The function returns a tuple of two lists, with the cropped input lists in order and the overflow buffers in the same order. I'm not sure if this is the best approach, of it it's better to zip them up so it returns ((list, overflow), (list, overflow)) instead.

Answer 1

I think the best would be to start with the shortest list and not the longest. In that case, any list that is shorter than the average and ideal number of items per list, can be copied completely and the remaining space will be recalculated and reassigned among the other lists.

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