Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
    
Out of curiosity, why do you want to do this? Is it a programming challenge? A practical solution to something? – holroy Jan 14 at 22:00
2  
@holroy Making an application for a local radio. Basically it should make a list of in what order dj-s need to air a commercial. The trick was that two consecutive commercials can't be read by the same person. – maikelnait Jan 14 at 22:11
    
First also posted the question here and got an answer. – maikelnait Jan 14 at 22:17
up vote 8 down vote accepted

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]
share|improve this answer
    
Why not just sort the list, instead of doing Counter, starmap, and repeat? This seems much more complicated than necessary. – Barry Jan 14 at 22:58
1  
The challenge with just sorting the list is for an odd sized list and a value that repeats exactly (len(list)+1)/2 there is a solution but it requires that you start with that element. If that element is not the lowest value then just sorting doesn't work, e,g. [1,2,3,3,3] has a solution [3,1,3,2,3] but just a sorted list would give [1,3,2,3,3] – AChampion Jan 15 at 0:36
    
Ztane, is it you? – coderodde Feb 3 at 15:12
1  
@coderodde ack! – Antti Haapala Feb 4 at 5:43

Using the great itertools module, the first half of your function could be rewritten in 3 lines. But first:

Do not modify alist in place if you intend to return a new list

Sometimes functions modify variables in place, sometimes they return a result, but they rarely do so when the input and the output are this tightly coupled. In your case, you sort alist in place but do not use it to store the end result. It's bad practice and you should choose either one or the other.

Since you already expect your function to return a result, I'd go this route and not modify alist at all. If you choose the other route, however, be sure to document the behaviour. Using docstrings for instance.

Use itertools to simplify the logic

I’ll present you two functions that will handle you two first blocks of code pretty easily. They basically just do what you reinvented out-of-the-box:

  • groupby which is directly doing the grouping of your first block;
  • zip_longest which can easily do the flattening of your groups; you’ll need to remove None values using a list-comprehension, for instance.

Use pop to remove elements out of a list

Instead of getting an element, inserting it elsewhere and deleting it, you should use pop on a list to get the element and remove it at the same time. The logic can be simplified.

Flaw?

It seems to me that for i in range(len(unord_list)-1, -1, -1): will leave some value at the end that doesn't satisfy your condition (for some inputs). You may want to decrease the index only if you didn't move elements

Proposed solution

from itertools import groupby, zip_longest

def unorder(a_list):
    groups = [list(g) for _, g in groupby(sorted(a_list))]
    groups.sort(key=len)
    flattened = [elem for group in zip_longest(*groups)
                 for elem in group if elem is not None]

    idx = -1
    end = -len(flattened)
    while idx > end:
        if flattened[idx] == flattened[idx-1]:
            reference = flattened.pop(idx)
            for j, element in enumerate(flattened):
                if not j and reference != element:
                    flattened.insert(0, reference)
                    break
                elif reference != element and reference != flattened[j+1]:
                    flattened.insert(j+1, reference)
                    break
        else:
            idx -= 1

    return flattened

Which gives:

>>> a = [1,1,1,1,2,2,2,2,3,3,3,4,4,4,4,4,4,4]
>>> unorder(a)
[4, 3, 4, 1, 4, 2, 4, 3, 1, 2, 4, 3, 1, 2, 4, 1, 2, 4]
share|improve this answer

Don't write docstrings in the middle of functions. It is tempting to use multiline strings as comments, but it's unvonventional and the time saved is not worth the displeased looks you'll get.

Your function is a bit too long. Typically when functions get long one should think of splitting them up. This does another good thing; it moves declarations closer to their usage point.

For example, one might now have

def group_same(alist):
    """
    Groups consecutive equal elements in a list,
    producing a list of lists.
    """
    multi_lvl_list = []

    start = 0
    for i in range(len(alist)):
        ...

    return multi_lvl_list

def interleave_lists(multi_lvl_list):
    """
    Creates a list formed from taking one element
    from the front of each list in the input list in turn,
    and repeating until all lists are empty.
    """

    unord_list = []
    while len(multi_lvl_list) > 0:
        ...

    return unord_list

def unorder(alist):
    alist.sort()
    multi_lvl_list = group_same(alist)
    multi_lvl_list.sort(key=len)

    unord_list = interleave_lists(multi_lvl_list)

    # 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):
        ...

    return unord_list

Instead of generating multi_lvl_list in group_same and interleave_lists, yeild elements sequentially from them. Turn them to lists at call-point if needed.

def group_same(alist):
    """
    Groups consecutive equal elements in a list,
    producing a list of lists.
    """
    start = 0
    for i in range(len(alist)):
        if i == len(alist)-1:
            if alist[i] != alist[i-1]:
                yield [alist[i]]
            else:
                yield alist[start:]
        elif alist[i] != alist[i+1]:
            yield alist[start:i+1]
            start = i+1
        i += 1

def interleave_lists(multi_lvl_list):
    """
    Creates a list formed from taking one element
    from the front of each list in the input list in turn,
    and repeating until all lists are empty.
    """

    while len(multi_lvl_list) > 0:
        for idx, val in enumerate(multi_lvl_list):
            yield val.pop()
            if len(val) == 0:
                del multi_lvl_list[idx]

group_same much more easily expressed with itertools.groupby:

def group_same(alist):
    """
    Groups consecutive equal elements in a list,
    producing a list of lists.
    """
    return (list(group) for _, group in groupby(alist))

Heck, I'd inline this again.

Now, your

while len(multi_lvl_list) > 0:
    for idx, val in enumerate(multi_lvl_list):
        yield val.pop()
        if len(val) == 0:
            del multi_lvl_list[idx]

doesn't quite work as expected which causes

unorder([1, 2, 3, 4, 5, 6])
#>>> [1, 3, 5, 2, 6, 4]

This is because del messes with the internal index in the list. You should always try to avoid changing the length of a list you're iterating over, even if that means dropping idiomatic tools like enumerate and using indexes instead. Luckily I don't think this will actually ever hurt you.

Note that a Counter's most_common will get you this much more quickly.

interleave_lists is roundrobin from the itertools recipes, so roundrobin should be used instead.

def roundrobin(*iterables):
    "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
    # Recipe credited to George Sakkis
    pending = len(iterables)
    nexts = cycle(iter(it).__next__ for it in iterables)
    while pending:
        try:
            for next in nexts:
                yield next()
        except StopIteration:
            pending -= 1
            nexts = cycle(islice(nexts, pending))

For the next part, note that cyclic shifts like this are not at all fast on lists, so should be strongly avoided. But note also that you can avoid it entirely by just being more intelligent about how you produce values.

from collections import Counter
from heapq import heapify, heappop, heapreplace

def unorder(alist):
    groups = Counter(alist).most_common()
    groups = [(-count, elem) for elem, count in groups]
    heapify(groups)

    count = 0
    while groups:
        if count == 0:
            count, elem = heappop(groups)
        else:
            count, elem = heapreplace(groups, (count, elem))

        yield elem
        count += 1

    for _ in range(-count):
        yield elem

This creates a heap of length-element pairs (equivalent to your list), only with the length inverted so it acts as a max heap and not a min heap. It will yield the most common element that isn't the previous element at any given time, maximizing the chance that the most repeated element will be used up by the end.

This is not as brilliant as Antti Haapala's solution, though.

share|improve this answer

Antti Haapala's insight that the item groups need to be processed in decreasing order of their length is central. Barry's comment is also justified in the sense that the problem can be solved by sorting and simple Python primitives, without mastery of powerful library modules. Below is a such solution:

def mix(seq):
    """Returns sequence seq so permuted that neighboring items are different.

       If this cannot be done, prints out a message and returns None.
    """

    # Operate on a sorted copy of seq:
    s = sorted(seq)  
    m = len(s) // 2   # mid index of s

    # Partition s in disjoint sequences a, b and c:
    i = m-1
    while i >= 0 and s[i] == s[m]: i -= 1

    a = s[0:i+1]    # items smaller than s[m] (can be empty)

    j = m + 1
    while j < len(s) and s[j] == s[m]: j += 1

    b = s[i+1:j]    # items equal with s[m]
    c = s[j:]       # items bigger than s[m] (can be empty)

    # Rename a, b and c in decreasing order of their length as f, g, and h:
    [h,g,f] = sorted([a,b,c], key=len)

    if len(f) > len(g) + len(h) + 1:
        # Not enough other items to place them btw those of f[]
        print("Cannot re-arrange the sequence", seq)
        return None 

    # Merge the items into s, taking them alternatingly from f, g and h,  
    # maintaining the invariant len(f) >= len(g) >= len(h)
    i = 0
    while i < len(s):   
    # invariant: items s[0:i] are placed OK
        s[i], i = f.pop(), i+1
        if i == len(s): break   # all items have been placed
        s[i], i = g.pop(), i+1
        # maintain invariant:
        if len(h) > len(g):
            if len(f) >= len(h):
                f, g, h = f, h, g
            else:  # len(h) > len(f)
                f, g, h = h, f, g
    return s

What would be interesting is whether the problem could be solved in linear time, that is, without resorting to (operations which are asymptotically equivalent to) sorting. My conjecture is 'no', but I have no proof for it.

Edit: Linear time is sufficient: Instead of sorting, the median around which we partition the sequence (in disjoint sub-sequences a, b and c) could be selected in linear time (Blum, Floyd, Pratt, Rivest & Tarjan, 1973). Rest of the algorithm remains as before, and works in linear time wrt the length of the sequence. (This does not mean that applying a worst-case linear-time median selection would necessarily be a practically efficient solution, though.)

share|improve this answer
    
My intuition of the necessity of sorting was wrong: Instead of sorting, a similar partitioning (into disjoint sub-sequences a, b and c) could be done around the /median/ of the sequence, which can be selected in linear time (Blum, Floyd, Pratt, Rivest & Tarjan, 1973). Rest of the algorithm remains as before, all of which is linear-time wrt the length of the input sequence. (This does not mean that partitioning around the median would necessarily be a /practically/ reasonable solution, though.) – Pekka Kilpeläinen Feb 3 at 14:22

A simple algorithm that uses heapq.

  • Construct heap with (-count+1, value) [Negative count provides the appropriate priority as heapq returns lowest first]
  • Pop from heap if not the previous element add to result and increase count and if <0 push back to the heap
  • Else pop 2nd element from heap add to result, push first element back to heap (same count), increase count of 2nd element and push back to the heap (if <0).
  • Rinse and repeat until no heap

from collections import Counter
import heapq

q = [(-c+1, v) for v, c in Counter([1,2,2,3,1,3,3]).items()]
heapq.heapify(q)
result = []

while q:
    c, v = heapq.heappop(q)
    if q and result and v == result[-1]:
        c, v = heap.heapreplace(q, (c, v))
    result.append(v)
    if c < 0:
        heapq.heappush(q, (c+1, v))
print(result)

Output:

[3, 1, 2, 3, 1, 2, 3]
share|improve this answer

Most of the permutations are good

Just going through all the permutations and finding where the condition is met is very fast for random lists.

The caveat is that some rare kinds of input (where there are many repetitions) will take way longer than average.

The big plus of this code is that it is incredibly simple:

from itertools import permutations

def all_neighbours_are_different(xs):
    return all(x != xs[i + 1] for i, x in enumerate(xs[:-1]))

def first(predicate, xs):
    return next(x for x in xs if predicate(x))

def unorder(xs):
    """
    Order the list `xs`, so that each element
    is not the same as the element that comes after or before it.
    """
    return list(first(all_neighbours_are_different, permutations(xs)))

I made some profiling with random data and it is very fast (the first column is the list length, the second the time taken):

2 4.352100040705409e-05
4 3.856900002574548e-05
8 4.207900019537192e-05
16 5.015199985791696e-05
32 5.9092999435961246e-05
64 7.938700036902446e-05
128 0.00011464399995020358
256 0.0002037069998550578
512 0.0003584179994504666
1024 0.0006946479998077848
2048 0.0015121830001589842
4096 0.002861821999431413
8192 0.00595371300005354
16384 0.010749521999969147
32768 0.022186172000147053
65536 0.04303188100038824
131072 0.0926356569998461
262144 0.18285627200020826
524288 0.3520253420001609
1048576 0.7203067009995721
2097152 1.3996731180004645
4194304 2.7669079550005335
8388608 5.440445696999632

Only profiling with your real-life data will tell you if your inputs slow this code down too much.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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