如何高效生成无旋转重复的列表全排列？

这个问题我之前做组合算法优化时碰到过——先全量生成再去重的思路，在列表长度超过5之后资源消耗会飙升，完全没必要。我们可以通过固定锚点元素的方式，从生成逻辑上直接规避旋转重复的排列。

核心思路 #

旋转重复的本质是：把某个排列的前k个元素移到末尾，得到的新排列和原排列是旋转等价的。那我们只要保证所有合法排列都以同一个固定元素开头，就能彻底排除旋转重复项——因为任何旋转后的排列的第一个元素都不是我们选定的锚点，自然不会被生成。

举个例子：对于列表[1,2,3]，我们选定1作为锚点，只生成以1开头的排列。这样最终只会得到[1,2,3]和[1,3,2]，像[2,3,1]、[3,1,2]这类旋转结果根本不会被纳入生成流程。

具体实现步骤 #

• 选定锚点：可以选列表中的最小值（或者第一个出现的特定元素，只要保证旋转等价类中只有一个排列会以它开头）。如果列表有重复元素，建议选第一个出现的目标值，避免因为重复锚点导致的额外重复。
• 生成剩余元素的全排列：把锚点从原列表中移除，对剩下的n-1个元素进行常规全排列生成。
• 拼接锚点与子排列：将锚点放在每个子排列的最前面，得到的就是无旋转重复的全排列集合。

Python代码示例 #

def generate_non_rotational_perms(arr):
    # 处理边界情况
    if len(arr) <= 1:
        return [arr]
    
    # 选定锚点：这里用第一个出现的最小值作为锚点
    anchor = min(arr)
    first_anchor_idx = arr.index(anchor)
    
    # 移除锚点，得到剩余元素列表
    remaining_elements = arr[:first_anchor_idx] + arr[first_anchor_idx+1:]
    
    # 递归生成剩余元素的全排列
    sub_perms = generate_non_rotational_perms(remaining_elements)
    
    # 拼接锚点和子排列，得到最终结果
    result = [[anchor] + perm for perm in sub_perms]
    
    return result

# 测试用例
print(generate_non_rotational_perms([1,2,3]))
# 输出: [[1, 2, 3], [1, 3, 2]]

print(generate_non_rotational_perms([1,1,2]))
# 输出: [[1, 1, 2], [1, 2, 1]]

处理含重复元素的场景 #

如果原列表有重复元素（比如[1,1,2]），上面的方法已经能避免旋转重复，但如果需要同时避免元素重复导致的排列重复（比如重复生成完全一样的排列），可以在生成子排列时加入去重逻辑，比如用集合存储已生成的排列（注意要把列表转成元组才能存入集合）：

def generate_non_rotational_perms_without_duplicates(arr):
    if len(arr) <= 1:
        return [arr]
    
    anchor = min(arr)
    first_anchor_idx = arr.index(anchor)
    remaining_elements = arr[:first_anchor_idx] + arr[first_anchor_idx+1:]
    
    sub_perms = generate_non_rotational_perms_without_duplicates(remaining_elements)
    
    # 用集合去重
    unique_sub_perms = list({tuple(perm) for perm in sub_perms})
    # 转回列表并拼接锚点
    result = [[anchor] + list(perm) for perm in unique_sub_perms]
    
    return result

为什么这个方法高效？ #

常规全排列的数量是n!，而无旋转重复的排列数量是(n-1)!（每个旋转等价类有n个元素，总共有n!/n = (n-1)!个等价类）。我们的方法直接生成(n-1)!个排列，完全没有多余的计算，时间复杂度从O(n!)降到了O((n-1)!)，空间效率也同步提升。

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