Skip to content

Instantly share code, notes, and snippets.

@zwegner

zwegner/flopsort.py

Created Jul 27, 2020
Embed
What would you like to do?
Quick+dumb way to sort an array to try and maximize Hamming distance between adjacent elements
import random
def hamming(a, b):
x = a ^ b
c = 0
while x:
x &= x - 1
c += 1
return c
def score(l):
weights = [hamming(a, b) for [a, b] in zip(l, l[1:])]
print(weights)
return sum(weights)
def flop_sort(lst):
for i in range(10000):
# Randomly partition
mid = random.randint(2, len(lst) - 2)
[first, second] = [lst[:mid], lst[mid:]]
# Get the endpoints of each segment
[a, b, c, d] = [first[0], first[-1], second[0], second[-1]]
# Find the best arrangement of segments
weights = [(hamming(a, c), 0), (hamming(a, d), 1),
(hamming(b, c), 2), (hamming(b, d), 3)]
best = max(weights)[1]
if best == 0: lst = first[::-1] + second
elif best == 1: lst = second + first
elif best == 2: lst = first + second
elif best == 3: lst = first + second[::-1]
return lst
N = 32
# Anti-Gray code
l = [a ^ (a >> 1) ^ (N - 1 if a & 1 else 0) for a in range(N)]
print(l)
print(score(l))
# Flop sort
l = flop_sort(list(range(N)))
print(l)
print(score(l))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.