CODEWITHSUNDEEP
pythonpermutation
anon_swe
anon_swe

Reputation: 9345

Generate all permutations without duplicates by rotation

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!

Upvotes: 4

Views: 969

Answers (3)

Kelly Bundy
Kelly Bundy

Reputation: 27588

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)

Upvotes: 2

root-11
root-11

Reputation: 1806

Since itertools.permutations is based on a cycle of combinations, the most effective solution is to iterate until the first item changes.

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

All subsequent iterations will be repetitions after the first item has changed.

Here are all permutations of [1,2,3,4]:

(1, 2, 3, 4)  # 1
(1, 2, 4, 3)  # 2
(1, 3, 2, 4)  # 3
(1, 3, 4, 2)  # 4
(1, 4, 2, 3)  # 5
(1, 4, 3, 2)  # 6

(2, 1, 3, 4)  # rotation of 4
(2, 1, 4, 3)  # rotation of 6
(2, 3, 1, 4)  # rotation of 5
(2, 3, 4, 1)  # rotation of 1
(2, 4, 1, 3)  # rotation of 3
(2, 4, 3, 1)  # rotation of 2

(3, 1, 2, 4) # r. of 2
(3, 1, 4, 2) # r. of 5
(3, 2, 1, 4) # r. of 6
(3, 2, 4, 1) # r. of 3
(3, 4, 1, 2) # r. of 1
(3, 4, 2, 1) # r. of 4

(4, 1, 2, 3) # r. of 1
(4, 1, 3, 2) # r. of 3
(4, 2, 1, 3) # r. of 4
(4, 2, 3, 1) # r. of 5
(4, 3, 1, 2) # r. of 2
(4, 3, 2, 1) # r. of 6

And as one may observe, all repetitions start once the first item changes.

Upvotes: 0

user2357112
user2357112

Reputation: 280535

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)

Upvotes: 3

Related Questions