Reorder a list in Python to avoid repeats

Question

I am trying to check if a list has any consecutive repeating elements and then reorder it such that the repeats are avoided. If that is impossible, then return False. For example:

checkRepeat([1,2])
Out[61]: [1, 2]

checkRepeat([1,2,2])
Out[62]: [2, 1, 2]

checkRepeat([1,2,2,1,1])
Out[63]: [1, 2, 1, 2, 1]

checkRepeat([1,2,2,1,1,3,3,3,3])
Out[64]: [1, 3, 1, 3, 2, 1, 3, 2, 3]

checkRepeat([1,2,2,1,1,3,3,3,3,3])
Out[65]: [3, 1, 3, 2, 3, 1, 3, 1, 3, 2]

checkRepeat([1,2,2,1,1,3,3,3,3,3,3])
Out[66]: [3, 1, 3, 1, 3, 1, 3, 2, 3, 2, 3]

checkRepeat([1,2,2,1,1,3,3,3,3,3,3,3])
Out[67]: False

Here is what I have. Is there a more elegant solution?

from itertools import groupby
from collections import Counter

def checkRepeat(lst):
    """Returns a list that has no repeating elements. Return False if such a list can't be found"""

    def hasRepeat(lst):
        """Returns true if there are any repeats"""
        return len([x[0] for x in groupby(lst)]) < len(lst)


    offset=numIter=0        
    if Counter(lst).most_common()[0][1]*2 > len(lst)+1: #checks if it will be impossible to find a working order
        return False

    while hasRepeat(lst):
        for i,curElt in enumerate(lst):
            try:
                if lst[i]==lst[i+1]:
                    lst[i+1],lst[(i+offset) % len(lst)] = lst[(i+offset) % len(lst)],lst[i+1] #swap j+1 with j+offset. wrap around the list
            except:
                break
        offset+=1
        numIter+=1
    return lst

Answer 1

Ideally a function will return a particular type of value. Python may be dynamic and allow you to return anything, but it's less surprising behaviour if you don't return two types of value. Instead, consider returning None or an empty list. Both of which will still evaluate as False when tested because of Python's truthiness. I'd personally suggest None, as an empty list might be mistaken for a useable list. Python will automatically use None as the return value in the absence of any other argument, so just using return returns None.

You should use snake_case for naming variables and functions, so checkRepeat should be check_repeat. I also don't like lst as a name. It's good that you're avoiding shadowing the built in list, but lst is unclear and can look like 1st. Perhaps iterable or source could be better names.

hasRepeat doesn't need to be a nested function, you could have it separated as it's own. Having it nested implies that you're trying to do a more complicated structure when really it's just because you call hasRepeat in checkRepeat. Also, checkRepeat isn't a good name as it's actually removing repeating values (if it can). Instead perhaps something like reorder_repeats? It would not be the clearest name because it's not an easy process to describe, but the docstring can provide help there too.

You should have spaces either side of your mathermatical operators, it makes them more readable and is recommended by the style guide. So this:

offset=numIter=0        

should be this:

offset = numIter = 0        

Also try to avoid inline comments, they make lines exceedingly long. They should be used sparingly for short comments. If your comment is a sentence it will almost always need its own line. The style guide also says to keep below 79 characters per line, which this comment invalidates:

if Counter(lst).most_common()[0][1]*2 > len(lst)+1: #checks if it will be impossible to find a working order

Split it onto the line above and it's much more readable.

# Check if it will be impossible to find a working order
if Counter(lst).most_common()[0][1] * 2 > len(lst) + 1:

Instead of curElt try the name element or item. Shortened words often make for odd names that people can easily interpret differently to you. Except that you don't end up using this value at all. Instead you access elements by their index, which I personally think is more readable in this case and better, but then you could just loop with this:

    for i in range(len(source)):

What's the point of numIter? It's the exact same value of offset but never even used? If it was a testing value you should remove it now. While we're on it, I don't entirely understand offset, a comment about it would be helpful when you're incrementing the values.

Don't use a bare except. It's very bad practice because you might ignore all sorts of errors that you should really be paying attention to. In this case, it seems like IndexError is what you're expectin to happen, so use that specifically.

The line where you swap values is too long and hard to read, instead you should calculate the index of your second value on the line before:

            if lst[i] == lst[i+1]:
                index = (i + offset) % len(lst)  # Wrap around the list
                lst[i+1], lst[index] = lst[index], lst[i+1] 

Now that it's clear that index is the same value on either side, it's obvious that you're swapping values. You can make this comment inline since it's a brief note about the meaning of an unusual calculation.

Here's how I'd put the script together:

from itertools import groupby
from collections import Counter

def has_repeat(source):
    """Returns true if there are any repeats"""

    return len([x[0] for x in groupby(source)]) < len(source)

def check_repeat(source):
    """Returns a list that has no repeating elements or None if such a list can't be found"""

    # Check if it will be impossible to find a working order
    if Counter(source).most_common()[0][1] * 2 > len(source) + 1:
        return

    offset = 0        
    while has_repeat(source):
        for i in range(len(source)):
            try:
                if source[i] == source[i+1]:
                    index = (i + offset) % len(source)  # Wrap around the list
                    source[i+1], source[index] = source[index], source[i+1]
            except IndexError:
                break
        offset += 1
    return source

Answer 2

1. Bugs

1. checkRepeat fails on an empty list:

   >>> checkRepeat([])
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
       if Counter(lst).most_common()[0][1]*2 > len(lst)+1:
   IndexError: list index out of range
   

2. On some inputs checkRepeat goes into an infinite loop, the simplest case being:

   >>> checkRepeat([1, 1, 1, 0, 0])
   ^C
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
     File "cr107630.py", line 17, in checkRepeat
       for i,curElt in enumerate(lst):
   KeyboardInterrupt
   

   It was clear that there was a risk of this happening, because you have a while loop with a condition, but no assurance that the body will make any progress towards meeting the condition.

   So I ran a simple test case:

   >>> from itertools import count
   >>> for i in count():
   ...     print(i, checkRepeat([1] * (i + 1) + [0] * i)
   

   and this immediately revealed the problem.

2. Fixing the bug

How can we be sure always to make progress? Well, one approach is to search for a safe place to swap each repeated item to, like this:

def repeat_free(seq):
    """Return a permutation of seq with no adjacent repeated items,
    or raise ValueError if this is impossible.

    """
    n = len(seq)
    if n < 2:
        return seq
    if Counter(seq).most_common(1)[0][1] > (n + 1) // 2:
        raise ValueError("No repeat-free permutation possible")
    seq = list(seq)    # Take a copy.
    i = 0
    while i < n - 1:
        i += 1
        a = seq[i - 1]
        if a == seq[i]:
            # Remove element and find somewhere safe for it to go.
            del seq[i - 1:i]
            for j in range(n):
                if (j == 0 or a != seq[j - 1]) and (j == n - 1 or a != seq[j]):
                    seq.insert(j, a)
                    if j > i:
                        i -= 1
                    break
            else:
                # Condition above assures that there is somewhere safe.
                assert(False)
    return seq

The code is a bit complex and fiddly with all those indexes, but at least it works reliably. It would be nicer (and more efficient) with a doubly-linked list, but there's no doubly-linked list in the standard Python library.

An alternative approach is to read the values directly out of the counter:

def repeat_free(seq):
    """Return a permutation of seq with no adjacent repeated items,
    or raise ValueError if this is impossible.

    """
    n = len(seq)
    if n < 2:
        return seq
    counts = Counter(seq)
    if counts.most_common(1)[0][1] > (n + 1) // 2:
        raise ValueError("No repeat-free permutation possible")
    result = []
    last = object()
    for _ in range(n):
        for item, _ in counts.most_common(2):
            if item != last:
                result.append(item)
                counts[item] -= 1
                last = item
                break
        else:
            # One of the two most common items must differ from last.
            assert(False)
    # All items must be used.
    assert not +counts
    return result

This is nicer code, but note that it does not preserve object identity:

>>> repeat_free([1, 1.0, 2, 2.0])
[1, 2, 1, 2]