Detect if a list is a circular permutation of a given list

circular_shift.py

#!/usr/bin/env python3

''' Detect if a list is a circular permutation of a given list

    Written by PM 2Ring 2017.11.01
'''

from random import seed, randrange
seed(42)

def is_circ_perm(a, b):
    ''' Is b a circular permutation of a? '''
    alen = len(a)
    if alen != len(b):
        return False
    a2 = a + a
    for i in range(alen):
        if b == a2[i:i+alen]:
            return True
    return False

def lexico_permute(seq):
    ''' Lexicographically ordered permutations of seq.
        Handles repeated items in seq correctly.
        See https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
    '''
    a = sorted(seq)
    n = len(a) - 1
    while True:
        yield a[:]

        #1. Find the largest index j such that a[j] < a[j + 1]
        for j in range(n-1, -1, -1):
            if a[j] < a[j + 1]:
                break
        else:
            return

        #2. Find the largest index k greater than j such that a[j] < a[k]
        v = a[j]
        for k in range(n, j, -1):
            if v < a[k]:
                break

        #3. Swap the value of a[j] with that of a[k].
        a[j], a[k] = a[k], a[j]

        #4. Reverse the tail of the sequence
        a[j+1:] = a[j+1:][::-1]

# Test

num = 8
a = [randrange(10) for _ in range(num)]
print('Original', a)
# Generate all permutations, but only print the circular shifts.
for i, b in enumerate(lexico_permute(a), 1):
    b = list(b)
    if is_circ_perm(a, b):
        print(i, b)
print('Total number of permutations:', i)