http://stackoverflow.com/questions/25285792/make-a-list-as-unsorted-as-possible

results.txt

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
--------------------------------------------------------------------------------

tests.py

########################


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)

working_generator.py

"""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)