Python实现任意长度句子数组按字符阈值均匀分桶（不拆句）

这个是典型的一维装箱优化问题，要求不拆分句子、单桶总字符数不超过阈值、桶间负载尽可能均匀，你完全可以跳过原本第二步的迭代调整逻辑，用更简单高效的方案实现：

推荐方案：降序贪心放置法 #

这个方法实现成本极低，均匀性表现也能覆盖绝大多数场景需求：

• 预处理阶段：先给每个句子计算字符长度，同时校验是否存在单个句子长度超过阈值N的情况，这类非法输入要提前处理，否则问题无解
• 排序阶段：把所有句子按照字符长度从大到小排序
• 装桶阶段：每次取当前最长的句子，放到当前总长度最小、且放入后总长度不超过阈值N的桶里，如果没有符合条件的桶就新建一个桶

基础实现（Python，适合万级以下句子量） #

def allocate_sentences(sentences: list[str], max_threshold: int) -> list[list[str]]:
    # 预处理：计算每个句子长度，校验非法输入
    sent_with_len = []
    for s in sentences:
        s_len = len(s)
        if s_len > max_threshold:
            raise ValueError(f"存在单句长度超过阈值：长度{s_len}，内容「{s[:20]}...」")
        sent_with_len.append((-s_len, s))  # 负号方便升序排序等价于长度降序
    
    # 按长度降序排序
    sent_with_len.sort()
    buckets = []  # 每个元素为(桶当前总长度, 桶内句子列表)

    for neg_len, s in sent_with_len:
        s_len = -neg_len
        # 查找能放入的、总长度最小的桶
        min_total = float('inf')
        target_idx = -1
        for idx, (total, s_list) in enumerate(buckets):
            if total + s_len <= max_threshold and total < min_total:
                min_total = total
                target_idx = idx
        if target_idx != -1:
            # 放入目标桶
            buckets[target_idx] = (min_total + s_len, buckets[target_idx][1] + [s])
        else:
            # 新建桶
            buckets.append((s_len, [s]))
    
    # 只返回桶内的句子列表
    return [b[1] for b in buckets]

堆优化实现（Python，适合十万级以上句子量） #

如果句子量很大，可以用小根堆优化查找最小桶的步骤，时间复杂度从O(M*K)降到O(M log K)（M为句子总数，K为最终桶数量）：

import heapq

def allocate_sentences_heap(sentences: list[str], max_threshold: int) -> list[list[str]]:
    sent_with_len = []
    for s in sentences:
        s_len = len(s)
        if s_len > max_threshold:
            raise ValueError(f"存在单句长度超过阈值：长度{s_len}，内容「{s[:20]}...」")
        sent_with_len.append((-s_len, s))
    
    sent_with_len.sort()
    heap = []  # 小根堆，每个元素为(桶当前总长度, 桶id)
    bucket_content = []  # 按id存储桶内句子列表

    for neg_len, s in sent_with_len:
        s_len = -neg_len
        placed = False
        temp_store = []
        # 从堆顶取最小的桶判断是否能放入
        while heap:
            cur_total, bid = heapq.heappop(heap)
            if cur_total + s_len <= max_threshold:
                # 可以放入，更新桶信息
                bucket_content[bid].append(s)
                heapq.heappush(heap, (cur_total + s_len, bid))
                placed = True
                break
            else:
                # 暂时存起来，之后放回堆
                temp_store.append((cur_total, bid))
        # 把刚才取出来的不能放的桶放回堆
        for item in temp_store:
            heapq.heappush(heap, item)
        if not placed:
            # 新建桶
            new_bid = len(bucket_content)
            bucket_content.append([s])
            heapq.heappush(heap, (s_len, new_bid))
    
    return bucket_content

方案优势 #

• 没有复杂的迭代调整逻辑，代码易维护，出问题好排查
• 先放大句子再补小句子的逻辑，天然避免了大句子没地方放的问题，最终桶之间的总长度差通常不会超过最长的短句长度，均匀性表现很好
• 严格满足所有约束：不会拆分句子，所有桶的总长度都不会超过设定的阈值N

内容的提问来源于stack exchange，提问作者rubmz