Sorting a circular list of binary necklaces by rotational hamming distance

Question

I am trying to sort lists of binary necklaces in circle format. So that elements on the opposite side of the circle have the greatest max rotational hamming distance. And neighbors have the smallest.

I am hopping around the circle adding up the rotational max hamming distance. I test all permutations and select the permutation with the small total hamming distance around the circumference.

All fine and dandy but permutations get to be too much calculation for n>9 I want to run this on n=66, for example.

So I am wondering if there is a more efficient way to sort the circle according to my criteria. All necklaces are of equal length.

here my code:

import sys
import itertools
from scipy.spatial.distance import hamming

def rotate(strg, n):
    return strg[n:] + strg[:n]

def combinantorial(lst):
    count = 0
    index = 1
    pairs = []
    for element1 in lst:
        for element2 in lst[index:]:
            pairs.append((element1, element2))
        index += 1

def permute(items):
    length = len(items)
    def inner(ix=[]):
        do_yield = len(ix) == length - 1
        for i in range(0, length):
            if i in ix: #avoid duplicates
                continue
            if do_yield:
                yield tuple([items[y] for y in ix + [i]])
            else:
                for p in inner(ix + [i]):
                    yield p
    return inner()



def maxhammer(list1, list2):
    themaxham = 0
    hamcheck = 0

    for i in range(len(list1)):
        hamcheck = hamming(list(list1),list(rotate(list2, i)))*len(list(list1));
        if hamcheck > themaxham:
            themaxham = hamcheck
    return themaxham


lines_list = map(str.strip, sys.stdin);


permutationslist = permute(lines_list[1:])

minlength = 999999;
linecount = 0;


for line in permutationslist:
    listtemp = list(line)
    listtemp.insert(0, lines_list[0])
    line = tuple(listtemp)
    circlelength = 0;
    for i in range(len(line)):
        circlelength+= maxhammer(line[i], line[(i+1)%len(line)])
    if circlelength < minlength:
        minlength = circlelength
        winner = line
        print(line)
        print("CIRCLELENGTH:",circlelength)
print("WINNER:")
print(winner)

I run it like so:

cat lyndonlist.txt | grep -x '.\{5\}'  python minmaxhamBRUTEFORCE.py 

This will send all 5 bit Lyndon words in to the program

output:

('10000', '11000', '10100', '11100', '11010', '11110')
('CIRCLELENGTH:', 22.0)
('10000', '11000', '10100', '11100', '11110', '11010')
('CIRCLELENGTH:', 20.0)
('10000', '11000', '11010', '11110', '11100', '10100')
('CIRCLELENGTH:', 18.0)
WINNER:
('10000', '11000', '11010', '11110', '11100', '10100')

This gives me a cycle of words with lexicographic opposites on the opposite sides of the cycle.

Here is a diagram of the winning output:

The Elements with rotational Hamming Max between each shown