Permutation of list in Python so that list[x] != list[x+1]

Question

Basically I need to order a list, so that an element is not the same as the element that comes after or before it. I searched for a solution but couldn't find one so I wrote this function myself.

For example, [1,2,2,3,1,3,3] should come out as [3,1,2,3,1,2,3], [3,2,3,1,2,3,1] or [2,1,3,1,3,2,3] and so on.

def unorder(alist):
    multi_lvl_list = []
    unord_list = []

    alist.sort()

    # makes a new list that holds lists where same elements
    # are grouped together
    start = 0
    for i in range(len(alist)):
        if i == len(alist)-1:
            if alist[i] != alist[i-1]:
                multi_lvl_list.append([alist[i]])
            else:
                multi_lvl_list.append(alist[start:])
        elif alist[i] != alist[i+1]:
            multi_lvl_list.append(alist[start:i+1])
            start = i+1
        i += 1

    multi_lvl_list.sort(key=len)

    '''
    goes over every list and pops out one element to a third list
    if there are many same elements they will be put 
    to the end of the list
    '''
    while len(multi_lvl_list) > 0:
        for idx, val in enumerate(multi_lvl_list):
            unord_list.append(val.pop())
            if len(val) == 0:
                del multi_lvl_list[idx]

    '''
    go over the list in reverse. if x == x-1 try to put x in the
    beginning of the list. becourse there are 
    more likely different elements
    '''
    for i in range(len(unord_list)-1, -1, -1):
        if unord_list[i] == unord_list[i-1]:
            for j in range(len(unord_list)):
                if j == 0:
                    if unord_list[i] != unord_list[0]:
                        unord_list.insert(0, unord_list[i])
                        del unord_list[i+1]
                elif unord_list[i] != unord_list[j] and unord_list[i] != unord_list[j+1]:
                    unord_list.insert(j+1, unord_list[i])
                    del unord_list[i+1]
        else:
            break

    return unord_list

It seems to work in cases where it's possible to make such a list, but I'm pretty sure there is a more efficient way and the code can be optimized.

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

Answer 2

A simple algorithm that uses heapq.

• Construct heap with (-count, value) [Negative count provides the appropriate priority as heapq returns lowest first]
• Pop from heap if no previous element or exhaust previous element
• Else pop element from heap (and push previous element to heap - heapreplace)
• Add element to results
• Increase count
• Rinse and repeat until no heap
• Add any remaining count of the last element (i.e. no solution) - alternatively you could raise an error.

---

from collections import Counter
import itertools as it
import heapq

def unorder(alist):
    q = [(-c, v) for v, c in Counter(alist).items()]
    heapq.heapify(q)

    c = 0
    while q:
        c, v = heapq.heappop(q) if c == 0 else heapq.heapreplace(q, (c, v))
        yield v
        c += 1

    if c > 0:  # No solution - add remaining values to the end
        yield from it.repeat(v, -c)

print(list(unorder([1, 2, 2, 3, 1, 3, 3])))

Output:

[3, 1, 2, 3, 1, 2, 3]