如何从海量排列中随机选取子集，规避内存与性能问题？

针对你遇到的从n个作业的全排列中无重复随机选取k个排列（n=15时全排列无法全部存入内存）的问题，以下是可行的优化方案及问题分析：

问题根源分析 #

1. 原代码直接生成全排列列表会导致内存溢出，因为15!≈1.3×10¹²，完全无法存储。
2. 你尝试的方法1速度慢的核心原因：用列表的in操作检查重复是线性遍历，随着已选排列数量增加，每次检查的时间成本会线性上升，导致整体效率极低。
3. 方法2随机性差的原因：仅对初始序列打乱后取其前k个排列，本质是从单一初始序列的排列子集采样，无法覆盖全排列的随机分布。

可行解决方案 #

方案1：优化去重逻辑（高效无重复采样） #

利用集合的O(1)查找特性替代列表的线性查找，大幅提升重复检查效率。同时直接用random.sample生成随机排列（当采样长度等于原列表长度时，random.sample等价于Fisher-Yates洗牌，生成的是真随机排列）。

import random

jobs = list(self.machines[m])
num_selected = 你的目标选取数量
selected_perms = set()

while len(selected_perms) < num_selected:
    # 生成随机排列并转为可哈希的元组存入集合
    perm_tuple = tuple(random.sample(jobs, len(jobs)))
    selected_perms.add(perm_tuple)

# 若需要列表格式，可转换为列表
selected_perms = list(selected_perms)

• 优势：严格保证无重复，效率极高。由于15!的规模极大，即使选取10000个排列，重复概率几乎为0，循环会快速结束。
• 注意：必须将排列转为元组（列表不可哈希，无法存入集合）。

方案2：无检查快速采样（近似无重复） #

如果可以接受极小的重复概率（实际场景中几乎不可能发生），可以直接生成k个随机排列，省去重复检查步骤，速度达到最快。

import random

jobs = list(self.machines[m])
num_selected = 你的目标选取数量
selected_perms = [tuple(random.sample(jobs, len(jobs))) for _ in range(num_selected)]

• 重复概率估算：选取1000个排列时，重复概率约为3.8×10⁻⁷，完全可以忽略不计。
• 适用场景：对排列唯一性要求不是绝对严格，追求极致效率的场景。

方案3：Lehmer编码映射（精准无重复采样） #

如果需要绝对无重复且避免循环等待（极端场景下k接近全排列数量），可以利用Lehmer编码将排列与唯一整数映射，随机选取k个不重复整数后转换为排列。不过对于n=15的场景，方案1已经足够高效，此方案仅作扩展参考：

import random
import math

def lehmer_to_permutation(lehmer, elements):
    elements = elements.copy()
    permutation = []
    for num in lehmer:
        permutation.append(elements.pop(num))
    return tuple(permutation)

jobs = list(self.machines[m])
n = len(jobs)
num_selected = 你的目标选取数量

# 生成k个不重复的随机整数（范围0到n!-1）
max_index = math.factorial(n) - 1
selected_indices = random.sample(range(max_index + 1), num_selected)

# 将整数转换为Lehmer编码，再转为排列
selected_perms = []
for idx in selected_indices:
    lehmer = []
    remaining = idx
    for i in range(n-1, -1, -1):
        fact = math.factorial(i)
        lehmer.append(remaining // fact)
        remaining %= fact
    selected_perms.append(lehmer_to_permutation(lehmer, jobs))

• 优势：直接生成无重复的随机排列，无需循环检查。
• 缺点：实现相对复杂，n较大时（如n=15）计算阶乘会得到大整数，但Python支持大整数运算，仍可正常运行。

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