Java实现从列表随机抽取元素且保留各组元素原有相对顺序的方法

方案1：加权随机选择法（最优时间复杂度，支持均匀采样） #

这是通用场景下的最优实现，不限组数、不限每组长度，且能保证所有合法排列的采样概率完全相等：

• 第一步：将原始列表按前缀分组为三个先进先出队列：qA = [A1, A2, A3]、qB = [B1, B2, B3]、qC = [C1, C2, C3]，所有非空队列归入候选集合
• 第二步：每次从候选集合中按队列剩余长度加权随机选中一个队列，取出队首元素放入结果列表
• 第三步：如果选中的队列取完元素后为空，就从候选集合中删除，重复第二步直到所有队列清空

举个计算示例：第一次选择时三个队列长度都是3，每个被选中的概率为3/(3+3+3)=1/3；如果第一次选中C队列取走C1，剩余队列长度为3、3、2，第二次选择时A、B的选中概率为3/8，C的选中概率为2/8，以此类推。
该方法时间复杂度为O(n)，n为总元素数，全程无额外冗余计算。

方案2：拒绝采样法（实现最简单，适合小数据量） #

如果总元素数量不大，用该方法写代码成本最低，几乎不会出现逻辑错误：

• 第一步：给每组元素分配递增的组内序号，比如A组三个元素的组内序号为1、2、3，B、C组规则一致
• 第二步：给所有元素随机生成一个全局唯一的浮点数标记
• 第三步：按全局浮点数从小到大排序所有元素，检查同组元素的组内序号是否保持递增，符合要求就输出结果，不符合就重新生成浮点数重复排序校验。
  该方法属于拒绝采样，数据量增大时重复校验的概率会明显升高，效率会快速下降。

代码示例（Python版，方案1实现） #

import random
from collections import deque

def random_constrained_shuffle(raw_list):
    # 按前缀分组
    groups = {}
    for item in raw_list:
        prefix = item[0]
        if prefix not in groups:
            groups[prefix] = deque()
        groups[prefix].append(item)
    candidate_queues = list(groups.values())
    result = []
    while candidate_queues:
        # 按剩余长度加权随机选择队列
        weights = [len(q) for q in candidate_queues]
        selected_q = random.choices(candidate_queues, weights=weights, k=1)[0]
        result.append(selected_q.popleft())
        # 空队列移出候选集
        if not selected_q:
            candidate_queues.remove(selected_q)
    return result

# 测试调用
raw_list = ["A1","A2","A3","B1","B2","B3","C1","C2","C3"]
print(random_constrained_shuffle(raw_list))

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