2

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!

3
  • 1
    can you show us the code you've written using itertools? Jul 26, 2018 at 6:04
  • 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, 2018 at 6: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, 2018 at 6:15

5 Answers 5

2

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.

2
  1. Think of a "fixed point" on the necklace.
  2. arrange for the lowest numbered bead, 1, to be rotated to this point
  3. 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)]

1
  • I could have used int(factorial(ilength - 1)) instead of the // division sub-expression.
    – Paddy3118
    Jul 26, 2018 at 22:37
2

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

1

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)

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, 2018 at 6:42
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]]
4
  • 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, 2018 at 6:24
  • So I am looking for output such as [1,3,2,4] from an input of [1,2,3,4]
    – Joe
    Jul 26, 2018 at 6: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, 2018 at 6: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, 2018 at 7:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.