如何为数组的每种可能排列生成唯一索引？

核心方法：阶数编码（Factorial Number System） #

对于含n个唯一元素的数组排列，阶数编码可以将每个排列映射到0到n!-1之间的唯一整数，这个整数就是所需的唯一索引——因为n个元素的总排列数恰好是n!，刚好能覆盖所有可能的排列。

具体实现步骤（以示例数组为例） #

假设原数组为[1,2,3,4,5,6,7,8]，待编码排列为[6,3,4,7,1,2,8,5]：

• 初始化索引index = 0，创建原数组的有序副本remaining = [1,2,3,4,5,6,7,8]
• 逐个遍历排列中的元素：
  1. 找到当前元素在remaining中的位置k（从0开始计数）
  2. 计算k * (n - i - 1)!（i为当前遍历的索引，从0开始；n为数组长度），将结果累加到index
  3. 从remaining中移除当前元素
• 遍历完成后，index就是该排列对应的唯一索引

Python代码实现 #

排列转索引 #

import math

def perm_to_index(perm, original):
    n = len(perm)
    remaining = original.copy()
    index = 0
    for i in range(n):
        pos = remaining.index(perm[i])
        index += pos * math.factorial(n - i - 1)
        remaining.pop(pos)
    return index

# 测试示例
original_arr = [1,2,3,4,5,6,7,8]
test_perm = [6,3,4,7,1,2,8,5]
print(perm_to_index(test_perm, original_arr))  # 输出对应唯一索引

索引转排列（反向操作） #

如果需要从索引还原对应排列，可使用阶数编码的逆过程：

def index_to_perm(index, original):
    n = len(original)
    remaining = original.copy()
    permutation = []
    for i in range(n):
        fact_val = math.factorial(n - i - 1)
        pos = index // fact_val
        permutation.append(remaining[pos])
        remaining.pop(pos)
        index = index % fact_val
    return permutation

注意事项 #

• 原数组必须包含唯一元素，否则无法保证索引的唯一性
• 对于n=8的场景，总排列数为40320，索引范围是0到40319，普通整数类型即可存储
• 只要original参数保持固定的元素顺序，就能确保同一排列始终对应同一个索引

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