多项式时间内从超指数规模受限排列集均匀采样

要实现从{0, 1, ..., n-1}的所有**长度≤n、元素无重复的排列（含空序列）**中均匀采样，核心思路是分两步：先按对应比例选序列长度，再生成该长度的均匀随机排列，全程仅需O(n)时间，完全规避阶乘级枚举。

步骤拆解 #

1. 计算各长度排列数的前缀和

首先我们需要明确不同长度的排列数在总样本中的占比：

• 长度为k的排列数为 P(n,k) = n × (n-1) × ... × (n-k+1)（k=0时为1，对应空序列）
• 总样本数 T = sum_{k=0}^n P(n,k)
• 我们可以递推计算前缀和数组prefix_sum，其中prefix_sum[k]表示长度从0到k的排列数总和：

  def compute_prefix_sum(n):
      prefix = [1]  # k=0的情况，空序列仅1个
      current_perm = 1
      for k in range(1, n+1):
          current_perm *= (n - k + 1)
          prefix.append(prefix[-1] + current_perm)
      return prefix
  

2. 按比例选择序列长度k

生成一个1到T之间的均匀随机整数r，找到最小的k使得prefix_sum[k] ≥ r——这一步确保选到长度k的概率恰好等于该长度排列数占总样本数的比例。对于n不大的情况，线性扫描足够简单：

import random

def choose_k(prefix_sum):
    total = prefix_sum[-1]
    r = random.randint(1, total)
    for k in range(len(prefix_sum)):
        if prefix_sum[k] >= r:
            return k

3. 生成长度为k的均匀随机排列

用Fisher-Yates洗牌的前k步生成无重复的随机排列，保证每个k长度排列被选中的概率均等：

def generate_k_permutation(n, k):
    arr = list(range(n))
    for i in range(k):
        # 从i到n-1中随机选一个位置交换到i
        j = random.randint(i, n-1)
        arr[i], arr[j] = arr[j], arr[i]
    return tuple(arr[:k])  # 用元组匹配示例格式

4. 整合为完整函数

def sample_bounded_permutations(n):
    if n == 0:
        return ()
    prefix_sum = compute_prefix_sum(n)
    k = choose_k(prefix_sum)
    return generate_k_permutation(n, k)

正确性说明 #

整个采样过程的均匀性来自两点：

• 选择长度k的概率为P(n,k)/T，正好对应该长度排列数在总样本中的占比
• 每个k长度排列被生成的概率为1/P(n,k)
• 两者相乘得到每个有效样本被选中的概率为1/T，完全符合均匀采样的要求

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