通过旋转生成所有无重复的排列

Question

我试图生成列表的所有排列，但受到旋转不重复的约束。因此，如果我对长度为 3 的列表执行此操作，进行正常排列，我会同时得到

[1, 2, 3]

和

[2, 3, 1]

。但是，

[2, 3, 1]

只是

[1, 2, 3]

的旋转，所以我不想包含它。

我可以生成所有排列、循环并删除违反此约束的元素，但这似乎很浪费。

在考虑排列时我该如何做到这一点，而不是考虑所有排列然后删除重复的排列？

谢谢！

Answer 1

取下第一个元素，生成其他元素的排列，并将第一个元素粘回每个排列的前面。这将生成每个旋转等价类的一个代表，特别是原始第一个元素仍然是第一个的代表。

import itertools

def permutations(iterable):
    # Special case: empty iterable
    iterable = list(iterable)
    if not iterable:
        yield ()
        return

    first, *rest = iterable
    for subperm in itertools.permutations(rest):
        yield (first, *subperm)

Answer 2

与 user2357112 的 和 root-11 的 相同的原则，即保持第一个元素固定并排列所有其他元素。更快一点。

from itertools import permutations, islice
from math import factorial

def permutations_without_rotations(lst):
    return islice(permutations(lst), factorial(max(len(lst) - 1, 0)))

十个元素的时间：

  8.51 ± 0.04 ms  Kelly
 64.56 ± 0.54 ms  root_11
 90.87 ± 1.21 ms  user2357112

Python: 3.11.4 (main, Sep  9 2023, 15:09:21) [GCC 13.2.1 20230801]

基准脚本（在线尝试！）：

import itertools
from timeit import timeit
from statistics import mean, stdev
from collections import deque
from itertools import repeat
from itertools import permutations, islice
from math import factorial
import sys


def Kelly(lst):
    return islice(permutations(lst), factorial(max(len(lst) - 1, 0)))


def user2357112(iterable):
    # Special case: empty iterable
    iterable = list(iterable)
    if not iterable:
        yield ()
        return

    first, *rest = iterable
    for subperm in itertools.permutations(rest):
        yield (first, *subperm)


def root_11(seq):
    for i in itertools.permutations(seq):
        if i[0] != seq[0]:
            break
        yield i

funcs = user2357112, root_11, Kelly

times = {f: [] for f in funcs}
def stats(f):
    ts = [t * 1e3 for t in sorted(times[f])[:5]]
    return f'{mean(ts):6.2f} ± {stdev(ts):4.2f} ms '

for _ in range(25):
    for f in funcs:
        t = timeit(lambda: deque(f(range(10)), 0), number=1)
        times[f].append(t)

for f in sorted(funcs, key=stats):
    print(stats(f), f.__name__)

print('\nPython:', sys.version)