Skip to content

Instantly share code, notes, and snippets.

@gebrkn gebrkn/results.txt
Last active Aug 29, 2015

Embed
What would you like to do?
testing <function srgerg at 0x1069d99b0>
500 total, 0 faults in 0.013 sec
--------------------------------------------------------------------------------
testing <function heuster at 0x1069de500>
500 total, 0 faults in 0.004 sec
--------------------------------------------------------------------------------
testing <function coady at 0x1069de320>
500 total, 0 faults in 0.011 sec
--------------------------------------------------------------------------------
testing <function david_eisenstat at 0x1069de2a8>
500 total, 0 faults in 0.013 sec
--------------------------------------------------------------------------------
testing <function tobias_k at 0x1069de230>
500 total, 51 faults in 0.032 sec
--------------------------------------------------------------------------------
testing <function jojo at 0x1069de1b8>
500 total, 73 faults in 0.006 sec
--------------------------------------------------------------------------------
testing <function enrico_bacis at 0x1069de398>
500 total, 0 faults in 0.015 sec
--------------------------------------------------------------------------------
########################
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)
"""Verify that `non_adjacent_permutations` (for a lack of a better name)
generates all and unique permutations with no (or minimal number of) equal adjacent elements.
kudos @tobias_k http://stackoverflow.com/a/25286251/989121
"""
def non_adjacent_permutations(lst):
def generate(counts, total, last=None):
if not total:
yield ()
return
for n in counts:
if n != last and counts[n] > 0:
counts[n] -= 1
for p in generate(counts, total - 1, n):
yield (n,) + p
counts[n] += 1
counts = {}
for x in lst:
counts[x] = counts.get(x, 0) + 1
return generate(counts, len(lst))
##############################################################
import random, itertools
# 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 all_naive(a):
"""Generate good permutations naively."""
seen = set()
for p in itertools.permutations(a):
if evil(p) == 0 and p not in seen:
yield p
seen.add(p)
count = 50
tests = [[random.choice(items) for _ in range(size)] for _ in range(count)]
for a in tests:
x = sorted(all_naive(a))
y = sorted(non_adjacent_permutations(a))
assert x == y
print a, 'ok, nperms=', len(x)
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.