|
######################## |
|
|
|
|
|
from collections import Counter |
|
from heapq import heapify, heappop, heapreplace |
|
from itertools import repeat |
|
|
|
def srgerg(data): |
|
heap = [(-freq+1, value) for value, freq in Counter(data).items()] |
|
heapify(heap) |
|
|
|
freq = 0 |
|
result = list() |
|
while heap: |
|
freq, val = heapreplace(heap, (freq+1, val)) if freq else heappop(heap) |
|
result.append(val) |
|
result.extend(repeat(val, -freq)) |
|
return result |
|
|
|
from collections import Counter |
|
from bisect import bisect |
|
|
|
def enrico_bacis(lst): |
|
# use elements (-count, item) so bisect will put biggest counts first |
|
items = [(-count, item) for item, count in Counter(lst).most_common()] |
|
result = [] |
|
|
|
while items: |
|
count, item = items.pop(0) |
|
result.append(item) |
|
if count != -1: |
|
element = (count + 1, item) |
|
index = bisect(items, element) |
|
# prevent insertion in position 0 if there are other items |
|
items.insert(index or (1 if items else 0), element) |
|
|
|
return result |
|
|
|
def jojo(lst): |
|
my_list = sorted(lst) |
|
length = len(my_list) |
|
odd_ind = length%2 |
|
odd_half = (length - odd_ind)/2 |
|
for i in range(odd_half)[::2]: |
|
my_list[i], my_list[odd_half+odd_ind+i] = my_list[odd_half+odd_ind+i], my_list[i] |
|
|
|
#this is just for the limit case where the abundance of the most frequent is half of the list length |
|
if max([my_list.count(val) for val in set(my_list)]) + 1 - odd_ind > odd_half: |
|
max_val = my_list[0] |
|
max_count = my_list.count(max_val) |
|
for val in set(my_list): |
|
if my_list.count(val) > max_count: |
|
max_val = val |
|
max_count = my_list.count(max_val) |
|
while max_val in my_list: |
|
my_list.remove(max_val) |
|
out = [max_val] |
|
max_count -= 1 |
|
for val in my_list: |
|
out.append(val) |
|
if max_count: |
|
out.append(max_val) |
|
max_count -= 1 |
|
if max_count: |
|
#print 'this is not working' |
|
return my_list |
|
#raise Exception('not possible') |
|
return out |
|
else: |
|
return my_list |
|
|
|
def tobias_k(lst): |
|
from collections import Counter |
|
|
|
def unsort2(counts, last=None): |
|
if sum(counts.values()): |
|
for n in counts: |
|
if n != last and counts[n] > 0: |
|
counts[n] -= 1 |
|
for perm in unsort2(counts, n): |
|
yield [n] + perm |
|
counts[n] += 1 |
|
else: |
|
yield [] |
|
|
|
# if no perfect permutation, return the original list |
|
return next(unsort2(Counter(lst)), lst) |
|
|
|
import collections |
|
import heapq |
|
|
|
class Sentinel: |
|
pass |
|
|
|
def david_eisenstat(lst): |
|
counts = collections.Counter(lst) |
|
heap = [(-count, key) for (key, count) in counts.items()] |
|
heapq.heapify(heap) |
|
output = [] |
|
last = Sentinel() |
|
while heap: |
|
minuscount1, key1 = heapq.heappop(heap) |
|
if key1 != last or not heap: |
|
last = key1 |
|
minuscount1 += 1 |
|
else: |
|
minuscount2, key2 = heapq.heappop(heap) |
|
last = key2 |
|
minuscount2 += 1 |
|
if minuscount2 != 0: |
|
heapq.heappush(heap, (minuscount2, key2)) |
|
output.append(last) |
|
if minuscount1 != 0: |
|
heapq.heappush(heap, (minuscount1, key1)) |
|
return output |
|
|
|
import collections, heapq |
|
|
|
def coady(lst): |
|
def nonadjacent(keys): |
|
heap = [(-count, key) for key, count in collections.Counter(keys).items()] |
|
heapq.heapify(heap) |
|
count, key = 0, None |
|
while heap: |
|
count, key = heapq.heapreplace(heap, (count, key)) if count else heapq.heappop(heap) |
|
yield key |
|
count += 1 |
|
for index in xrange(-count): |
|
yield key |
|
|
|
return list(nonadjacent(lst)) |
|
|
|
def heuster(lst): |
|
|
|
# Sort the list |
|
a = sorted(lst) |
|
|
|
# Put the element occurring more than half of the times in front (if needed) |
|
n = len(a) |
|
m = (n + 1) // 2 |
|
for i in range(n - m + 1): |
|
if a[i] == a[i + m - 1]: |
|
a = a[i:] + a[:i] |
|
break |
|
|
|
result = [None] * n |
|
|
|
# Loop over the first half of the sorted list and fill all even indices of the result list |
|
for i, elt in enumerate(a[:m]): |
|
result[2*i] = elt |
|
|
|
# Loop over the second half of the sorted list and fill all odd indices of the result list |
|
for i, elt in enumerate(a[m:]): |
|
result[2*i+1] = elt |
|
|
|
return result |
|
|
|
|
|
fns = [srgerg, heuster, coady, david_eisenstat, tobias_k, jojo, enrico_bacis] |
|
|
|
######################## |
|
|
|
import random, itertools, time |
|
|
|
# list items |
|
items = [1,2,3] |
|
|
|
# list size |
|
size = 7 |
|
|
|
def evil(a): |
|
"""evilness of the list - count of bad pairs.""" |
|
|
|
return sum(a[i-1] == a[i] for i in range(1, len(a))) |
|
|
|
def naive(a): |
|
"""Generate a good permutation naively.""" |
|
|
|
mina, mine = a, len(a) |
|
for p in itertools.permutations(a): |
|
e = evil(p) |
|
if e == 0: |
|
return p |
|
if e < mine: |
|
mina, mine = p, e |
|
return mina |
|
|
|
|
|
def test(fns, tests, verbose=True): |
|
"""Try the algorithm and see if it returns the optimal perm.""" |
|
|
|
print 'testing', fn |
|
print |
|
|
|
faults = 0 |
|
ts = 0 |
|
|
|
for a in tests: |
|
t = time.time() |
|
b = fn(a) |
|
ts += time.time() - t |
|
|
|
if len(b) != len(a): |
|
eb = 99 |
|
else: |
|
eb = evil(b) |
|
|
|
if verbose: |
|
print a, '->', b, eb, |
|
|
|
if eb: |
|
n = naive(a) |
|
en = evil(n) |
|
|
|
if eb > en: |
|
if verbose: |
|
print '***', n, en, |
|
faults += 1 |
|
|
|
if verbose: |
|
print |
|
|
|
print '%d total, %d faults in %.3f sec' % (len(tests), faults, ts) |
|
print '-' * 80 |
|
|
|
count = 500 |
|
tests = [[random.choice(items) for _ in range(size)] for _ in range(count)] |
|
|
|
for fn in fns: |
|
test(fn, tests, verbose=False) |
