10
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ What happens if a single element is repeated more than half the time in the list? e.g. [1, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]? \$\endgroup\$ – mgilson Jan 14 '16 at 21:28
  • 1
    \$\begingroup\$ In that case it will return just [3, 1, 3, 2, 3, 3, 3, 3, 3, 3, 3, 3], nothing more can be done. \$\endgroup\$ – maikelnait Jan 14 '16 at 22:01
9
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Tried it out. Works great and much more efficient. Thanks \$\endgroup\$ – maikelnait Jan 14 '16 at 21:59
  • \$\begingroup\$ You're welcome. When the time comes, remember to properly retire the question: up-vote the useful responses and accept your favourite answer. \$\endgroup\$ – Prune Jan 14 '16 at 22:03
  • \$\begingroup\$ When you said "efficient ways to ... maintain the ordering", I was expecting something like heapq. All that pop(0)-ing and insert-ing can get really slow if you have a lot of different elements in your list. \$\endgroup\$ – user2357112 supports Monica Jan 14 '16 at 22:58
  • \$\begingroup\$ Agreed; this is an entry-level solution in list manipulation. For long lists of elements, it's much faster to use heapq, set up a linked list, or simply recognize when you've used up enough elements that you can just cycle lazily through the remainder with impunity. \$\endgroup\$ – Prune Jan 14 '16 at 23:04
5
\$\begingroup\$

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]
|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.