Generate all permutations of a list without adjacent equal elements

This is along the lines of Thijser's currently incomplete pseudocode. The idea is to take the most frequent of the remaining item types unless it was just taken. (See also Coady's implementation of this algorithm.)

import collectionsimport heapqclass Sentinel:    passdef david_eisenstat(lst):    counts = collections.Counter(lst)    heap = [(-count, key) for key, count in counts.items()]    heapq.heapify(heap)    output = []    last = Sentinel()    while heap:        minuscount1, key1 = heapq.heappop(heap)        if key1 != last or not heap:            last = key1            minuscount1 += 1        else:            minuscount2, key2 = heapq.heappop(heap)            last = key2            minuscount2 += 1            if minuscount2 != 0:                heapq.heappush(heap, (minuscount2, key2))        output.append(last)        if minuscount1 != 0:            heapq.heappush(heap, (minuscount1, key1))    return output

Proof of correctness

For two item types, with counts k1 and k2, the optimal solution has k2 - k1 - 1 defects if k1 < k2, 0 defects if k1 = k2, and k1 - k2 - 1 defects if k1 > k2. The = case is obvious. The others are symmetric; each instance of the minority element prevents at most two defects out of a total of k1 + k2 - 1 possible.

This greedy algorithm returns optimal solutions, by the following logic. We call a prefix (partial solution) safe if it extends to an optimal solution. Clearly the empty prefix is safe, and if a safe prefix is a whole solution then that solution is optimal. It suffices to show inductively that each greedy step maintains safety.

The only way that a greedy step introduces a defect is if only one item type remains, in which case there is only one way to continue, and that way is safe. Otherwise, let P be the (safe) prefix just before the step under consideration, let P' be the prefix just after, and let S be an optimal solution extending P. If S extends P' also, then we're done. Otherwise, let P' = Px and S = PQ and Q = yQ', where x and y are items and Q and Q' are sequences.

Suppose first that P does not end with y. By the algorithm's choice, x is at least as frequent in Q as y. Consider the maximal substrings of Q containing only x and y. If the first substring has at least as many x's as y's, then it can be rewritten without introducing additional defects to begin with x. If the first substring has more y's than x's, then some other substring has more x's than y's, and we can rewrite these substrings without additional defects so that x goes first. In both cases, we find an optimal solution T that extends P', as needed.

Suppose now that P does end with y. Modify Q by moving the first occurrence of x to the front. In doing so, we introduce at most one defect (where x used to be) and eliminate one defect (the yy).

Generating all solutions

This is tobias_k's answer plus efficient tests to detect when the choice currently under consideration is globally constrained in some way. The asymptotic running time is optimal, since the overhead of generation is on the order of the length of the output. The worst-case delay unfortunately is quadratic; it could be reduced to linear (optimal) with better data structures.

from collections import Counterfrom itertools import permutationsfrom operator import itemgetterfrom random import randrangedef get_mode(count):    return max(count.items(), key=itemgetter(1))[0]def enum2(prefix, x, count, total, mode):    prefix.append(x)    count_x = count[x]    if count_x == 1:        del count[x]    else:        count[x] = count_x - 1    yield from enum1(prefix, count, total - 1, mode)    count[x] = count_x    del prefix[-1]def enum1(prefix, count, total, mode):    if total == 0:        yield tuple(prefix)        return    if count[mode] * 2 - 1 >= total and [mode] != prefix[-1:]:        yield from enum2(prefix, mode, count, total, mode)    else:        defect_okay = not prefix or count[prefix[-1]] * 2 > total        mode = get_mode(count)        for x in list(count.keys()):            if defect_okay or [x] != prefix[-1:]:                yield from enum2(prefix, x, count, total, mode)def enum(seq):    count = Counter(seq)    if count:        yield from enum1([], count, sum(count.values()), get_mode(count))    else:        yield ()def defects(lst):    return sum(lst[i - 1] == lst[i] for i in range(1, len(lst)))def test(lst):    perms = set(permutations(lst))    opt = min(map(defects, perms))    slow = {perm for perm in perms if defects(perm) == opt}    fast = set(enum(lst))    print(lst, fast, slow)    assert slow == fastfor r in range(10000):    test([randrange(3) for i in range(randrange(6))])

Pseudocode:

1. Sort the list
2. Loop over the first half of the sorted list and fill all even indices of the result list
3. Loop over the second half of the sorted list and fill all odd indices of the result list

You will only have p[i]==p[i+1] if more than half of the input consists of the same element, in which case there is no other choice than putting the same element in consecutive spots (by the pidgeon hole principle).

As pointed out in the comments, this approach may have one conflict too many in case one of the elements occurs at least n/2 times (or n/2+1 for odd n; this generalizes to (n+1)/2) for both even and odd). There are at most two such elements and if there are two, the algorithm works just fine. The only problematic case is when there is one element that occurs at least half of the time. We can simply solve this problem by finding the element and dealing with it first.

I don't know enough about python to write this properly, so I took the liberty to copy the OP's implementation of a previous version from github:

# Sort the lista = sorted(lst)# Put the element occurring more than half of the times in front (if needed)n = len(a)m = (n + 1) // 2for i in range(n - m + 1):    if a[i] == a[i + m - 1]:        a = a[i:] + a[:i]        breakresult = [None] * n# Loop over the first half of the sorted list and fill all even indices of the result listfor i, elt in enumerate(a[:m]):    result[2*i] = elt# Loop over the second half of the sorted list and fill all odd indices of the result listfor i, elt in enumerate(a[m:]):    result[2*i+1] = eltreturn result

The algorithm already given of taking the most common item left that isn't the previous item is correct. Here's a simple implementation, which optimally uses a heap to track the most common.

import collections, heapqdef nonadjacent(keys):    heap = [(-count, key) for key, count in collections.Counter(a).items()]    heapq.heapify(heap)    count, key = 0, None    while heap:        count, key = heapq.heapreplace(heap, (count, key)) if count else heapq.heappop(heap)        yield key        count += 1    for index in xrange(-count):        yield key>>> a = [1,2,3,3,2,2,1]>>> list(nonadjacent(a))[2, 1, 2, 3, 1, 2, 3]