如何在不生成全排列的情况下获取排列列表的第N个元素？

当处理大数量级的排列（比如12个元素）时，直接生成所有排列会耗尽内存——12!等于479001600，这个规模的列表根本无法在内存中存储。解决思路是利用阶乘的数学性质，逐个确定排列中的每个位置元素，完全不需要生成所有排列。

核心逻辑 #

• 对于n个元素的排列，每个固定首元素的子排列有(n-1)!个；
• 用当前N除以(n-1)!，得到的商就是当前剩余元素列表中要选的元素索引；
• 用N对(n-1)!取余，得到的余数作为下一轮的N值；
• 从剩余元素列表中取出对应索引的元素，添加到结果中；
• 重复上述步骤，直到所有元素都被选中。

Python 实现代码 #

import math

def get_nth_permutation(elements, n):
    elements = list(elements)
    permutation = []
    length = len(elements)
    
    # 预计算阶乘，避免重复计算
    factorials = [math.factorial(i) for i in range(length)]
    
    for i in range(length, 0, -1):
        fact = factorials[i-1]
        index = n // fact
        n = n % fact
        permutation.append(elements.pop(index))
    
    return tuple(permutation)

# 测试：对应range(3)的第3个（0-based）排列
print(get_nth_permutation(range(3), 3))  # 输出 (1, 2, 0)

# 处理range(12)的第12843175个元素
print(get_nth_permutation(range(12), 12843175))

注意事项 #

• 函数默认使用0-based索引，和Python标准库itertools.permutations的索引规则一致；如果需要1-based索引，只需把传入的n减1即可。
• 预计算阶乘能有效提升效率，避免循环中重复计算阶乘值。
• 若输入的n大于等于len(elements)!，需额外添加边界判断（比如抛出异常），避免索引越界。

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