Permutation of list in Python so that list[x] != list[x+1]
Would some pseudo-code be enough for you?

Build a collections.Counter (dictionary subclass) of the elements in the list.
output list = []
previous element = None
Loop for the length of the list:
    Pick the most frequent element that is not the previous one.
    Append this to the output list.
    Decrement its count.

return the output list


There are efficient ways to order the list count entries and maintain the ordering to facilitate choosing the proper next element.  A simple one is to order the initial list of counts by frequency.  At each iteration, choose the first element.  Decrement the count and sort it into the rest of the array, but insist on moving it down at least one position.  Repeat until all counts are 0.



I found a later use for this algorithm, so I coded it up.  I included a tracing print statement in the critical loop, so we can watch it in operation.

import collections


def unsort(in_list):
    size = len(in_list)
    if size == 0:
        return None

    # Build a list of pairs: value and count,
    #   in descending order of count.
    count_dict = collections.Counter(in_list)
    count_list = sorted(list(count_dict.iteritems()), key=lambda x: x[1], reverse=True)
    move_list = [[x[0], x[1]] for x in count_list]
    out_list = []

    # If the highest count is more than half the elements plus a half, no solution is possible.
    if move_list[0][1] * 2 &gt; size + 1:
        print "No solution possible"
        return

    # In each iteration, grab the element at the head of the list.
    # Place that value into the output queue.
    # Sort the element back into the list,
    #   moving it at least one element down to avoid repetition.
    for _ in range(size):
        first = move_list.pop(0)
        out_list.append(first[0])
        first[1] -= 1
        for i in range(1, len(move_list)):
            if first[1] &gt; move_list[i][1]:
                move_list.insert(i, first)
                break
        else:
            move_list.append(first)
        print move_list, out_list

    return out_list


# Main program -- test driver
a, b, c, = 'a', 'b', 'c'    # easier notation for test cases
test_case = [
    [],
    [c, c, b, b, b, a, b, c, b],
    [c, c, b, b, b, b, b, c, b],    # Too many b's'
]

for case in test_case:
    print unsort(case), '\n'


Output:

Input: []
None 

Input: ['c', 'c', 'b', 'b', 'b', 'a', 'b', 'c', 'b']
[['c', 3], ['b', 4], ['a', 1]] ['b']
[['b', 4], ['c', 2], ['a', 1]] ['b', 'c']
[['c', 2], ['b', 3], ['a', 1]] ['b', 'c', 'b']
[['b', 3], ['a', 1], ['c', 1]] ['b', 'c', 'b', 'c']
[['a', 1], ['b', 2], ['c', 1]] ['b', 'c', 'b', 'c', 'b']
[['b', 2], ['c', 1], ['a', 0]] ['b', 'c', 'b', 'c', 'b', 'a']
[['c', 1], ['b', 1], ['a', 0]] ['b', 'c', 'b', 'c', 'b', 'a', 'b']
[['b', 1], ['a', 0], ['c', 0]] ['b', 'c', 'b', 'c', 'b', 'a', 'b', 'c']
[['a', 0], ['c', 0], ['b', 0]] ['b', 'c', 'b', 'c', 'b', 'a', 'b', 'c', 'b']
['b', 'c', 'b', 'c', 'b', 'a', 'b', 'c', 'b'] 

Input: ['c', 'c', 'b', 'b', 'b', 'b', 'b', 'c', 'b']
No solution possible
None