Reordering a list in python so that no neighboring elements are equal

Basically I need to order a list, so that an element is not the same as the element that comes after or before it.

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.

I searched for a solution but couldn't find one so I wrote this function myself.

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 cas

As the Python version was not specified, I assume Python 3; for Python 2 you need to adjust the imports from itertools

There are a number of ways you can attack this problem. One way becomes apparent if we think of an input that has no solution, which would be if more than half + 1 (rounded up) of the elements would be equal to each other, e.g. you can find a solution for [1, 1, 1, 2, 2] but not for [1, 1, 1, 1, 2, 2].

The solution would be that you group the elements and sort them by decreasing group length, then interleave first half of the elements with the rest; so, if your list is [3, 2, 2, 1, 3, 1, 1], at first you need to somehow group them, then sort into decreasing order, so that you get for example [1, 1, 1, 3, 3, 2, 2]; then you split it into 2 almost equal parts: [1, 1, 1, 3] and [3, 2, 2], and interleave these into the result: [1, 3, 1, 2, 1, 2, 3].

There are many ways to write this algorithm, here is one, using Python standard library extensively:

from collections import Counter
from itertools import chain, repeat, starmap, zip_longest, islice

def funny_op(l):
    # use Counter to count the number of each distinct element, then
    # most_common() to sort them by decreasing frequency
    counts = Counter(l).most_common()

    # counts is a list of (element, count) pairs; with the example input
    # it could be [(1, 3), (3, 2), (2, 2)]

    # we then make an iterator that iterates over each distinct
    # element, by repeating each `element` `count` times
    sorted_els = chain.from_iterable(starmap(repeat, counts))

    # now, for example input sorted_els would be an iterator yielding 
    # 1, 1, 1, 3, 3, 2, 2

    # we split it into half; we round up so that the first
    # list gets the extra element
    halfway = (len(l) + 1) // 2

    # the elements that go to even indices

    even = list(islice(sorted_els, halfway))

    # and the remaining fill up the odd indices of the result list
    odd = sorted_els

    # then we interleave elements from even and odd. In case the 
    # original list had odd number of elements, there'd be an 
    # extra None, which we remove by islicing only len(l) elements;
    # and return the result as a list

    return list(islice(chain.from_iterable(zip_longest(even, odd)), len(l)))

To test:

print(funny_op([2, 2, 1, 1, 1]))

prints:

[1, 2, 1, 2, 1]

StackExchange Code Review Q#116821, answer score: 9