Python Algorithms: Necklace Generation / Circular Permutations

Question

I am struggling with generating circular permutations, or solving the "Necklace Problem" with Python. I am basically looking to generate all circular permutations of a list as efficiently as possible.

Basically, assume we have a list [1,2,3,4], I want to generate all unique permutations in a circular fashion. So:

[1,2,3,4], [1,3,2,4]

Would be considered different, whereas:

[1,2,3,4], [4,1,2,3] would be considered the same, as I am looking only for unique permutations of a circular list.

I have tried generating all permutations with itertools but this is very inefficient when using larger length lists.

As another example, consider a running loop songs, characterised by [1,2,3,4,5] playing on repeat. I am trying to come up with an algorithm to generate only unique orders. Obviously [1,2,3,4,5] and [4,5,1,2,3] would result in the same order.

Struggling and would appreciate some help to solve this problem!

Answer 1

The following code produces all permutations of the last n-1 numbers, prepending each permutation with the first element of the original list.

from itertools import permutations
circular_perms = [my_list[:1]+list(perm) for perm in permutations(my_list[1:])]

Where my_list is your initial list of values to generation all circular permutations of.