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!

Can you share what you have tried in itertools? And what length of elements are we talking about in your case? Itertools can generally be seen as an already pretty efficient implementation of most things... — dennlinger, Jul 26 '18 at 06:04
The issue is that I am not looking to generate all permutations, so using something like `perms = itertools.permutations(my_list)` is inefficient. I am looking to generate only unique permutations in a circular array. — Joe, Jul 26 '18 at 06:15

score 2 · Answer 1 · answered Jul 26 '18 at 06:59

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.

score 2 · Answer 2 · answered Jul 26 '18 at 22:27

Think of a "fixed point" on the necklace.
arrange for the lowest numbered bead, 1, to be rotated to this point
Then the only orders of the beads is all the permutations of items that start with 1

Because the itertool.permutations generator in Python has the first item in the input list varying the least in successive output, the following code just outputs all the solutions as seen when rotated to the fixed point above.

   
from itertools import permutations, islice
from math import factorial

items = [1, 2, 3 ,4]
ilength = len(items)
base_necklace_orders = list(islice(permutations(items), factorial(ilength) // ilength))
print(base_necklace_orders)
# [(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2)]

I could have used `int(factorial(ilength - 1))` instead of the `//` division sub-expression. — Paddy3118, Jul 26 '18 at 22:37

score 2 · Answer 3 · answered Sep 10 '19 at 16:15

2

There are two Python libraries (that I know of) which will generate combinatoric necklaces. They are Sage and SymPy.

answered Sep 10 '19 at 16:15

Daniel Ching

443
5
9

Serge Ballesta · Answer 4 · 2018-07-26T06:59:18.697

1

When you havea list of N elements, one of the circular permutations of the list is uniquely given by its first element. Than means that you will have exactly N circular permutation (including the original list), and you can pass from one to another by removing fist element and adding it at the end of the list.

You can easily build a generator for all the circular permutations of a list:

def circ_perm(lst):
    cpy = lst[:]                 # take a copy because a list is a mutable object
    yield cpy
    for i in range(len(lst) - 1):
        cpy = cpy[1:] + [cpy[0]]
        yield cpy

Demo:

>>> list(circ_perm([1,2,3,4]))
[[1, 2, 3, 4], [2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3]]

If what you want is the unique permutations when two permutations that are a ciruclar permution of the other one, you can still use the fact that a circular permutation is given by its first element and fix the first element and find all the permutations of what remains:

def uniq_perm(lst):
    gen = itertools.permutations(lst[1:])
    for end in gen:
        yield [lst[0]] + list(end)

Demo:

>>> list(uniq_perm([1,2,3,4]))
[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2]]

edited Jul 26 '18 at 06:59

answered Jul 26 '18 at 06:17

Serge Ballesta

143,923
11
122
252

I am actually looking to generate the unique permutations in a circular list. The output of your method produces those which I would need to exclude. – Joe Jul 26 '18 at 06:24
So I am looking for output such as [1,3,2,4] from an input of [1,2,3,4] – Joe Jul 26 '18 at 06:25
So basically the "necklace" problem. Say you have 5 unique beads on a necklace, how many different orders of the beads could you have, regardless of whether the necklace is rotated? – Joe Jul 26 '18 at 06:27
@joe: 4!. Generate all permutations which start with `1` (i.e. generate all permutations of the last `n-1` elements.) No two of these are rotations of each other because they all have `1` in the same place. I suspect that your real goal is different. – rici Jul 26 '18 at 07:22

score 1 · Answer 5 · answered Jul 26 '18 at 06:32

The complexity for making permutation is about O(n*n!), so for large number or list it would inefficient to generate all possible permutations, You can use backtracking to generating list permutation, I'll share a link may be this would help. The solution is based on the backtracking

   
def permute(a, l, r):
    if l == r:
        print(a)
    else:
        for i in range(l, r + 1):
            a[l], a[i] = a[i], a[l]
            permute(a, l + 1, r)
            a[l], a[i] = a[i], a[l]

data = [1,2,3,4,5]
n = len(data)
a = list(data)
permute(a, 0, n - 1)

Thank you, this appears to calculate all permutations, so [1,2,3,4,5] is generated, but so also is [5,4,3,2,1] for example. I am looking only for unique orders around a circular array. So no two elements should ever appear next to each other twice. — Joe, Jul 26 '18 at 06:42

Python Algorithms: Necklace Generation / Circular Permutations

5 Answers5

Linked