Generate all permutations without duplicates by rotation

Question

I'm trying to generate all permutations of a list subject to the constraint that there are no duplicates by rotation. So if I were doing this for lists of length 3, doing normal permutations I would get both [1, 2, 3] and [2, 3, 1]. However, [2, 3, 1] is just a rotation of [1, 2, 3] and so I don't want to include it.

I could generate all permutations, loop through and remove elements that violate this constraint but this seems wasteful.

How could I do this as I consider permutations, instead of considering all permutations and then removing duplicated ones?

Thanks!

Answer 1

Take the first element off, generate permutations of the other elements, and stick the first element back onto the front of every permutation. This will generate one representative of every rotational equivalence class, specifically the representative where the original first element is still first.

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

Same principle as user2357112's and root-11's, i.e., keeping the first element fixed and permuting all the others. Just faster.

from itertools import permutations, islice
from math import factorial

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

Times for ten elements:

  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]

Benchmark script (Attempt This Online!):

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)