基于模运算实现列表项轮询分配至槽位并保持弹出顺序的增量算法

需求说明 #

现有两个任务列表：

items = list(range(1, 20))
items2 = list(range(1, 20))

需将两个列表依次通过轮询（round robin）方式分配至3个槽位。要求从每个槽位弹出首项时，输出顺序与轮询存入的顺序一致，因此需要为长度不足的槽位添加填充值-1，最终期望得到如下结构的字典：

{0: [[1, 4, 7, 10, 13, 16, 19, 1, 4, 7, 10, 13, 16, 19]],
1: [[2, 5, 8, 11, 14, 17, -1, 2, 5, 8, 11, 14, 17]],
2: [[3, 6, 9, 12, 15, 18, -1, 3, 6, 9, 12, 15, 18]]}

问题现状 #

自行编写的代码运行后输出顺序不符合预期，原本应两次按1-19的顺序输出，但因缺少填充逻辑，第二个列表的输出顺序混乱。

尝试的代码 #

import math
from pprint import pprint

items = list(range(1, 20))
items2 = list(range(1, 20))
slots = {0: [[]], 1: [[]], 2: [[]]}


def assign_slots(items, slots):
  s = len(slots.keys())
  mina = 0
  wrap = False
  last = 0
  padding = {k: len(v[0]) for k, v in slots.items()}
  print("padding", padding)
  for item in range(0, len(items)):
    wrap = False
    r = math.floor(item / s)
    m = item % s

    if item >= s:
      wrap = True
      mina = len(slots[m][0])
      print(mina)
    if item < s and len(slots[item]) == 0:
      slots[item].append([items[item]])
      
    elif item < s and len(slots[item]) > 0:
      slots[item][0].append(items[item])
     
    elif wrap:
      print("value", items[item], "item is", item, "padding is", padding[m], "length is ", len(slots[m][0]), "r is", r)
   
      # for i in range(item, padding[m] - item):
      #   print("appending empty")
      #   slots[m][0].append(0)
      slots[m][0].append(items[item])
      

    else:

      slots[m][0].append([items[item]])
   
  return slots


results = assign_slots(items, slots)
results2 = assign_slots(items2, slots)

pprint(results2)
running = True
while running:
  has_items = False
  for slot in range(0, len(slots.keys())):
    if len(slots[slot][0]) > 0:
      has_items = True
      item = slots[slot][0]
      if len(item) > 0:
        work = item.pop(0)
        print("doing", work)

      else:
        print("empty")
        slots[slot].pop(0)
  if has_items == False:
    running = False
    break

最优增量实现方案 #

核心思路 #

1. 每次处理新列表前，先确保所有槽位的当前长度一致：将长度不足的槽位用-1填充到当前最长槽位的长度
2. 按轮询规则将新列表的元素依次添加到对应槽位
3. 处理完新列表后，再次将长度不足的槽位用-1填充到当前最长槽位的长度，保证所有槽位长度统一，后续弹出顺序一致

代码实现 #

from pprint import pprint

def assign_round_robin(items, slots, padding_val=-1):
    slot_count = len(slots)
    item_count = len(items)
    
    # 步骤1：先将所有槽位填充到当前最长长度，保证增量处理的一致性
    current_max_len = max(len(slot[0]) for slot in slots.values())
    for idx in slots:
        while len(slots[idx][0]) < current_max_len:
            slots[idx][0].append(padding_val)
    
    # 步骤2：轮询分配当前列表的元素
    for i, item in enumerate(items):
        slot_idx = i % slot_count
        slots[slot_idx][0].append(item)
    
    # 步骤3：再次统一所有槽位长度，填充不足的部分
    new_max_len = max(len(slot[0]) for slot in slots.values())
    for idx in slots:
        while len(slots[idx][0]) < new_max_len:
            slots[idx][0].append(padding_val)
    
    return slots

# 初始化槽位
slots = {0: [[]], 1: [[]], 2: [[]]}
items = list(range(1, 20))
items2 = list(range(1, 20))

# 依次分配两个列表
assign_round_robin(items, slots)
assign_round_robin(items2, slots)

# 查看最终槽位结构
pprint(slots)

# 模拟弹出首项，验证输出顺序
print("\n弹出顺序验证：")
running = True
while running:
    has_items = False
    for slot_idx in slots:
        slot_list = slots[slot_idx][0]
        if slot_list:
            has_items = True
            print(f"doing {slot_list.pop(0)}", end=" ")
    if not has_items:
        running = False
    else:
        print()

代码说明 #

• 增量处理逻辑：每次处理新列表时，先对齐所有槽位的当前长度，避免因历史长度差异导致的分配混乱
• 轮询分配：通过i % slot_count确定每个元素对应的槽位，符合round robin规则
• 统一长度：每次分配后再次对齐槽位长度，确保后续弹出时，每个槽位的元素能按轮询顺序依次输出

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