Wygeneruj wszystkie permutacje listy bez sąsiadujących równych elementów

Kiedy sortujemy listę, na przykład

a = [1,2,3,3,2,2,1]
sorted(a) => [1, 1, 2, 2, 2, 3, 3]

na wynikowej liście zawsze sąsiadują ze sobą równe elementy.

Jak mogę osiągnąć odwrotne zadanie - potasować listę tak, aby równe elementy nigdy (lub tak rzadko jak to możliwe) sąsiadowały ze sobą?

Na przykład w przypadku powyższej listy jednym z możliwych rozwiązań jest

p = [1,3,2,3,2,1,2]

Bardziej formalnie, biorąc pod uwagę listę a, wygeneruj jej permutację p, która minimalizuje liczbę par p[i]==p[i+1].

Ponieważ listy są duże, generowanie i filtrowanie wszystkich permutacji nie wchodzi w grę.

Pytanie dodatkowe: jak sprawnie wygenerować wszystkie takie permutacje?

Oto kod, którego używam do testowania rozwiązań: https://gist.github.com/gebrkn/9f550094b3d24a35aebd

UPD: Wybór zwycięzcy był trudnym wyborem, ponieważ wiele osób zamieściło doskonałe odpowiedzi. @VincentvanderWeele , @David Eisenstat , @Coady , @ enrico.bacis i @srgerg zapewniły funkcje, które bezbłędnie generują najlepszą możliwą permutację. @tobias_k i David również odpowiedzieli na pytanie bonusowe (wygeneruj wszystkie permutacje). Dodatkowe punkty dla Davida za dowód poprawności.

Najszybszy wydaje się kod z @VincentvanderWeele.

Jest to zgodne z obecnie niekompletnym pseudokodem Thijsera. Chodzi o to, aby wybrać najczęstszy z pozostałych typów przedmiotów, chyba że został właśnie wzięty. (Zobacz także implementację tego algorytmu przez Coady ).

import collections
import heapq


class Sentinel:
    pass


def 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

Dowód poprawności

Dla dwóch typów elementów, z liczebnościami k1 i k2, optymalne rozwiązanie ma k2 - k1 - 1 defektów, jeśli k1 <k2, 0 defektów, jeśli k1 = k2 i k1 - k2 - 1 defektów, jeśli k1> k2. Sprawa = jest oczywista. Pozostałe są symetryczne; każde wystąpienie elementu mniejszościowego zapobiega co najwyżej dwóm defektom z łącznej liczby k1 + k2 - 1 możliwych.

Ten zachłanny algorytm zwraca optymalne rozwiązania, zgodnie z następującą logiką. Przedrostek (rozwiązanie częściowe) nazywamy bezpiecznym, jeśli rozciąga się na rozwiązanie optymalne. Oczywiście pusty przedrostek jest bezpieczny, a jeśli bezpieczny przedrostek jest całym rozwiązaniem, to rozwiązanie jest optymalne. Wystarczy indukcyjnie pokazać, że każdy chciwy krok zapewnia bezpieczeństwo.

Jedynym sposobem, w jaki chciwy krok wprowadza wadę, jest pozostawienie tylko jednego typu przedmiotu, w którym to przypadku jest tylko jeden sposób, aby kontynuować, i jest to bezpieczny sposób. W przeciwnym razie niech P będzie (bezpiecznym) prefiksem tuż przed rozważanym krokiem, niech P będzie przedrostkiem tuż po, a S będzie optymalnym rozwiązaniem rozszerzającym P. Jeśli S również rozszerza P ', to gotowe. W przeciwnym razie niech P '= Px i S = PQ i Q = yQ', gdzie x i y to elementy, a Q i Q 'to sekwencje.

Załóżmy najpierw, że P nie kończy się na y. Z wyboru algorytmu, x występuje co najmniej tak często w Q jak y. Rozważ maksymalne podciągi Q zawierające tylko x i y. Jeśli pierwszy podciąg ma co najmniej tyle samo x co y, to można go przepisać bez wprowadzania dodatkowych defektów zaczynających się od x. Jeśli pierwszy podciąg ma więcej y niż x, to jakiś inny podciąg ma więcej x niż y i możemy przepisać te podciągi bez dodatkowych defektów, tak aby x było pierwsze. W obu przypadkach znajdujemy optymalne rozwiązanie T, które w razie potrzeby wydłuża P '.

Załóżmy teraz, że P kończy się na y. Zmodyfikuj Q, przesuwając pierwsze wystąpienie x na wierzch. W ten sposób wprowadzamy co najwyżej jedną wadę (gdzie kiedyś było x) i eliminujemy jedną wadę (yy).

Generowanie wszystkich rozwiązań

To jest odpowiedź Tobias_k plus wydajne testy w celu wykrycia, kiedy aktualnie rozważany wybór jest w jakiś sposób globalnie ograniczony. Asymptotyczny czas pracy jest optymalny, ponieważ narzut generowania jest rzędu długości wyjścia. Niestety najgorsze opóźnienie jest kwadratowe; można go zredukować do liniowego (optymalnego) z lepszymi strukturami danych.

from collections import Counter
from itertools import permutations
from operator import itemgetter
from random import randrange


def 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 == fast


for r in range(10000):
    test([randrange(3) for i in range(randrange(6))])

Pseudo kod:

1. Sortuj listę
2. Przewiń pierwszą połowę posortowanej listy i wypełnij wszystkie parzyste indeksy listy wyników
3. Przewiń drugą połowę posortowanej listy i wypełnij wszystkie nieparzyste indeksy listy wyników

Będziesz mieć tylko p[i]==p[i+1]wtedy, gdy więcej niż połowa danych wejściowych składa się z tego samego elementu, w którym to przypadku nie ma innego wyboru niż umieszczenie tego samego elementu w kolejnych miejscach (zgodnie z zasadą dziury pidgeonowej).

Jak wskazano w komentarzach, podejście to może powodować o jeden konflikt za dużo w przypadku, gdy jeden z elementów występuje co najmniej n/2raz (lub n/2+1nieparzysto n; uogólnia się to (n+1)/2)na parzyste i nieparzyste). Są co najwyżej dwa takie elementy, a jeśli są dwa, algorytm działa dobrze. Jedyny problematyczny przypadek ma miejsce, gdy jeden element występuje co najmniej w połowie przypadków. Możemy po prostu rozwiązać ten problem, znajdując element i zajmując się nim najpierw.

Nie wiem wystarczająco dużo o Pythonie, aby napisać to poprawnie, więc pozwoliłem sobie skopiować implementację poprzedniej wersji OP z github:

# Sort the list
a = sorted(lst)

# Put the element occurring more than half of the times in front (if needed)
n = len(a)
m = (n + 1) // 2
for i in range(n - m + 1):
    if a[i] == a[i + m - 1]:
        a = a[i:] + a[:i]
        break

result = [None] * n

# Loop over the first half of the sorted list and fill all even indices of the result list
for 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 list
for i, elt in enumerate(a[m:]):
    result[2*i+1] = elt

return result

Podany już algorytm zabrania najczęściej używanego elementu, który nie jest poprzednim, jest poprawny. Oto prosta implementacja, która optymalnie wykorzystuje stertę do śledzenia najczęstszych.

import collections, heapq
def 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]

Możesz wygenerować wszystkie „idealnie nieposortowane” permutacje (które nie mają dwóch równych elementów w sąsiadujących pozycjach) przy użyciu rekurencyjnego algorytmu śledzenia wstecznego. W rzeczywistości jedyną różnicą w generowaniu wszystkich permutacji jest śledzenie ostatniej liczby i odpowiednie wykluczanie niektórych rozwiązań:

def unsort(lst, last=None):
    if lst:
        for i, e in enumerate(lst):
            if e != last:
                for perm in unsort(lst[:i] + lst[i+1:], e):
                    yield [e] + perm
    else:
        yield []

Zauważ, że w tej formie funkcja nie jest zbyt wydajna, ponieważ tworzy wiele podlist. Możemy również przyspieszyć to, patrząc najpierw na najbardziej ograniczone liczby (te z największą liczbą). Oto znacznie wydajniejsza wersja wykorzystująca tylko countsliczby.

def unsort_generator(lst, sort=False):
    counts = collections.Counter(lst)
    def unsort_inner(remaining, last=None):
        if remaining > 0:
            # most-constrained first, or sorted for pretty-printing?
            items = sorted(counts.items()) if sort else counts.most_common()
            for n, c in items:
                if n != last and c > 0:
                    counts[n] -= 1   # update counts
                    for perm in unsort_inner(remaining - 1, n):
                        yield [n] + perm
                    counts[n] += 1   # revert counts
        else:
            yield []
    return unsort_inner(len(lst))

Możesz użyć tego do wygenerowania nextidealnej permutacji lub listzatrzymania ich wszystkich. Należy jednak pamiętać, że jeśli nie ma idealnie nieposortowanej permutacji, to ten generator w konsekwencji nie przyniesie żadnych wyników.

>>> lst = [1,2,3,3,2,2,1]
>>> next(unsort_generator(lst))
[2, 1, 2, 3, 1, 2, 3]
>>> list(unsort_generator(lst, sort=True))
[[1, 2, 1, 2, 3, 2, 3], 
 ... 36 more ...
 [3, 2, 3, 2, 1, 2, 1]]
>>> next(unsort_generator([1,1,1]))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Aby obejść ten problem, możesz użyć tego razem z jednym z algorytmów zaproponowanych w innych odpowiedziach jako rezerwy. Gwarantuje to zwrócenie idealnie nieposortowanej permutacji, jeśli taka istnieje, lub dobre przybliżenie w innym przypadku.

def unsort_safe(lst):
    try:
        return next(unsort_generator(lst))
    except StopIteration:
        return unsort_fallback(lst)

W Pythonie możesz wykonać następujące czynności.

Rozważ, że masz posortowaną listę l, możesz zrobić:

length = len(l)
odd_ind = length%2
odd_half = (length - odd_ind)/2
for i in range(odd_half)[::2]:
    my_list[i], my_list[odd_half+odd_ind+i] = my_list[odd_half+odd_ind+i], my_list[i]

Są to tylko operacje w miejscu i dlatego powinny być raczej szybkie ( O(N)). Zwróć uwagę, że zmienisz pozycję z l[i] == l[i+1]na, l[i] == l[i+2]więc kolejność, w której otrzymasz, nie jest przypadkowa, ale z tego, jak rozumiem pytanie, nie jest to przypadkowość, której szukasz.

Chodzi o to, aby podzielić posortowaną listę pośrodku, a następnie wymienić każdy inny element w dwóch częściach.

Do l= [1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5]tego prowadzil = [3, 1, 4, 2, 5, 1, 3, 1, 4, 2, 5]

Metoda nie pozwala pozbyć się wszystkich, l[i] == l[i + 1]gdy tylko zawartość jednego elementu jest większa lub równa połowie długości listy.

Chociaż powyższe działa dobrze, o ile liczba najczęściej występujących elementów jest mniejsza niż połowa rozmiaru listy, poniższa funkcja obsługuje również przypadki graniczne (słynny problem oddzielania po jednym), w którym każdy inny element zaczynający się od pierwszy musi być najbardziej obfity:

def no_adjacent(my_list):
    my_list.sort()
    length = len(my_list)
    odd_ind = length%2
    odd_half = (length - odd_ind)/2
    for i in range(odd_half)[::2]:
        my_list[i], my_list[odd_half+odd_ind+i] = my_list[odd_half+odd_ind+i], my_list[i]

    #this is just for the limit case where the abundance of the most frequent is half of the list length
    if max([my_list.count(val) for val in set(my_list)]) + 1 - odd_ind > odd_half:
        max_val = my_list[0]
        max_count = my_list.count(max_val)
        for val in set(my_list):
            if my_list.count(val) > max_count:
               max_val = val
               max_count = my_list.count(max_val)
        while max_val in my_list:
            my_list.remove(max_val)
        out = [max_val]
        max_count -= 1
        for val in my_list:
            out.append(val)
            if max_count:
                out.append(max_val)
                max_count -= 1
        if max_count:
            print 'this is not working'
            return my_list
            #raise Exception('not possible')
        return out
    else:
        return my_list

Oto dobry algorytm:

1. Przede wszystkim policzyć dla wszystkich liczb, jak często się pojawiają. Umieść odpowiedź na mapie.

2. posortuj tę mapę tak, aby liczby, które występują najczęściej, były pierwsze.

3. Pierwsza liczba Twojej odpowiedzi to pierwsza liczba na posortowanej mapie.

4. Ułóż mapę, tak aby pierwsza była teraz mniejsza.

Jeśli chcesz poprawić wydajność, poszukaj sposobów na zwiększenie wydajności etapu sortowania.

Odpowiadając na pytanie bonusowe: jest to algorytm znajdujący wszystkie permutacje zbioru, w których żadne sąsiednie elementy nie mogą być identyczne. Uważam, że jest to najbardziej wydajny algorytm pod względem koncepcyjnym (chociaż inne mogą być w praktyce szybsze, ponieważ przekładają się na prostszy kod). Nie używa brutalnej siły, generuje tylko unikalne permutacje, a ścieżki nieprowadzące do rozwiązań są odcinane w najwcześniejszym momencie.

Użyję terminu „bogaty pierwiastek” dla elementu w zestawie, który występuje częściej niż wszystkie inne elementy razem wzięte, a terminu „obfitość” dla liczby pierwiastków w obfitości pomniejszonej o liczbę innych elementów.
np. zbiór abacnie ma elementu obfitego, zbiory abacai aabcaamają ajako element obfity, a obfitość odpowiednio 1 i 2.

1. Zacznij od zestawu takiego jak:

aaabbcd

2. Oddziel pierwsze wystąpienia od powtórzeń:

pierwsze: abcd
powtarza: aab

3. Znajdź pierwiastek obfity w powtórzeniach, jeśli występują, i oblicz go:

bogaty element:
obfitość: 1

4. Wygeneruj wszystkie permutacje pierwszych, w których liczba elementów po elemencie występującym w nadmiarze jest nie mniejsza niż liczebność: (więc w przykładzie „a” nie może być ostatnim)

ABCD ABDC, acbd, ACDB, adbc, adcb, BACD, badc, bcad, bcda , bdac, BDCA ,
cabd, cadb, cbad, CBDA , cdab, cdba , dabc, dacb ABAC DBCA , dcab, DCBA

5. Dla każdej permutacji wstaw zestaw powtarzających się znaków jeden po drugim, przestrzegając następujących zasad:

5.1. Jeśli liczebność zbioru jest większa niż liczba elementów po ostatnim wystąpieniu dotychczas występującego elementu w permutacji, przejdź do następnej permutacji.
np. jeśli dotychczasowa permutacja wynosi abc, zestaw z licznymi elementami amożna wstawić tylko wtedy, gdy liczebność wynosi 2 lub mniej, więc aaaabcjest ok, aaaaabcnie jest.

5.2. Wybierz element z zestawu, którego ostatnie wystąpienie w permutacji jest pierwsze.
np. jeśli dotychczasowa permutacja jest abcbai jest ustawiona ab, wybierzb

5.3. Wstaw wybrany element przynajmniej 2 pozycje na prawo od jego ostatniego wystąpienia w permutacji.
np. podczas wstawiania bdo permutacji babcawyniki to babcbaibabcab

5.4. Powtórz krok 5 z każdą wynikową permutacją i resztą zestawu.

EXAMPLE:
set = abcaba
firsts = abc
repeats = aab

perm3  set    select perm4  set    select perm5  set    select perm6

abc    aab    a      abac   ab     b      ababc  a      a      ababac  
                                                               ababca  
                                          abacb  a      a      abacab  
                                                               abacba  
                     abca   ab     b      abcba  a      -
                                          abcab  a      a      abcaba  
acb    aab    a      acab   ab     a      acaba  b      b      acabab  
                     acba   ab     b      acbab  a      a      acbaba  
bac    aab    b      babc   aa     a      babac  a      a      babaca  
                                          babca  a      -
                     bacb   aa     a      bacab  a      a      bacaba  
                                          bacba  a      -  
bca    aab    -
cab    aab    a      caba   ab     b      cabab  a      a      cababa  
cba    aab    -

Ten algorytm generuje unikalne permutacje. Jeśli chcesz poznać całkowitą liczbę permutacji (gdzie abajest liczona podwójnie, ponieważ możesz zamienić a), pomnóż liczbę unikalnych permutacji przez współczynnik:

F = N ₁ ! * N ₂ ! * ... * N _n !

gdzie N to liczba wystąpień każdego elementu w zestawie. Dla zestawu abcdabcababyłoby to 4! * 3! * 2! * 1! lub 288, co pokazuje, jak nieefektywny jest algorytm generujący wszystkie permutacje, a nie tylko te unikalne. Aby wyświetlić wszystkie permutacje w tym przypadku, po prostu wymień unikalne permutacje 288 razy :-)

Poniżej znajduje się (raczej niezgrabna) implementacja w Javascript; Podejrzewam, że język taki jak Python może być lepiej przystosowany do tego typu rzeczy. Uruchom fragment kodu, aby obliczyć oddzielne permutacje wyrażenia „abrakadabra”.

// FIND ALL PERMUTATONS OF A SET WHERE NO ADJACENT ELEMENTS ARE IDENTICAL
function seperatedPermutations(set) {
    var unique = 0, factor = 1, firsts = [], repeats = [], abund;

    seperateRepeats(set);
    abund = abundance(repeats);
    permutateFirsts([], firsts);
    alert("Permutations of [" + set + "]\ntotal: " + (unique * factor) + ", unique: " + unique);

    // SEPERATE REPEATED CHARACTERS AND CALCULATE TOTAL/UNIQUE RATIO
    function seperateRepeats(set) {
        for (var i = 0; i < set.length; i++) {
            var first, elem = set[i];
            if (firsts.indexOf(elem) == -1) firsts.push(elem)
            else if ((first = repeats.indexOf(elem)) == -1) {
                repeats.push(elem);
                factor *= 2;
            } else {
                repeats.splice(first, 0, elem);
                factor *= repeats.lastIndexOf(elem) - first + 2;
            }
        }
    }

    // FIND ALL PERMUTATIONS OF THE FIRSTS USING RECURSION
    function permutateFirsts(perm, set) {
        if (set.length > 0) {
            for (var i = 0; i < set.length; i++) {
                var s = set.slice();
                var e = s.splice(i, 1);
                if (e[0] == abund.elem && s.length < abund.num) continue;
                permutateFirsts(perm.concat(e), s, abund);
            }
        }
        else if (repeats.length > 0) {
            insertRepeats(perm, repeats);
        }
        else {
            document.write(perm + "<BR>");
            ++unique;
        }
    }

    // INSERT REPEATS INTO THE PERMUTATIONS USING RECURSION
    function insertRepeats(perm, set) {
        var abund = abundance(set);
        if (perm.length - perm.lastIndexOf(abund.elem) > abund.num) {
            var sel = selectElement(perm, set);
            var s = set.slice();
            var elem = s.splice(sel, 1)[0];
            for (var i = perm.lastIndexOf(elem) + 2; i <= perm.length; i++) {
                var p = perm.slice();
                p.splice(i, 0, elem);
                if (set.length == 1) {
                    document.write(p + "<BR>");
                    ++unique;
                } else {
                    insertRepeats(p, s);
                }
            }
        }
    }

    // SELECT THE ELEMENT FROM THE SET WHOSE LAST OCCURANCE IN THE PERMUTATION COMES FIRST
    function selectElement(perm, set) {
        var sel, pos, min = perm.length;
        for (var i = 0; i < set.length; i++) {
            pos = perm.lastIndexOf(set[i]);
            if (pos < min) {
                min = pos;
                sel = i;
            }
        }
        return(sel);
    }

    // FIND ABUNDANT ELEMENT AND ABUNDANCE NUMBER
    function abundance(set) {
        if (set.length == 0) return ({elem: null, num: 0});
        var elem = set[0], max = 1, num = 1;
        for (var i = 1; i < set.length; i++) {
            if (set[i] != set[i - 1]) num = 1
            else if (++num > max) {
                max = num;
                elem = set[i];
            }
        }
        return ({elem: elem, num: 2 * max - set.length});
    }
}

seperatedPermutations(["a","b","r","a","c","a","d","a","b","r","a"]);

Chodzi o to, aby posortować elementy od najbardziej powszechnego do najmniej powszechnego, wybrać najbardziej powszechny, zmniejszyć jego liczbę i umieścić go z powrotem na liście z zachowaniem kolejności malejącej (ale unikając umieszczania ostatniego używanego elementu na pierwszym miejscu, aby uniknąć powtórzeń, gdy to możliwe) .

Można to zaimplementować za pomocą Counteri bisect:

from collections import Counter
from bisect import bisect

def unsorted(lst):
    # use elements (-count, item) so bisect will put biggest counts first
    items = [(-count, item) for item, count in Counter(lst).most_common()]
    result = []

    while items:
        count, item = items.pop(0)
        result.append(item)
        if count != -1:
            element = (count + 1, item)
            index = bisect(items, element)
            # prevent insertion in position 0 if there are other items
            items.insert(index or (1 if items else 0), element)

    return result

Przykład

>>> print unsorted([1, 1, 1, 2, 3, 3, 2, 2, 1])
[1, 2, 1, 2, 1, 3, 1, 2, 3]

>>> print unsorted([1, 2, 3, 2, 3, 2, 2])
[2, 3, 2, 1, 2, 3, 2]

1. Sortuj listę.
2. Wygeneruj „best shuffle” listy za pomocą tego algorytmu

Poda minimum pozycji z listy w ich pierwotnym miejscu (według wartości pozycji), więc spróbuje, na przykład, odłożyć 1, 2 i 3 z dala od ich posortowanych pozycji.

Zacznij od posortowanej listy o długości n. Niech m = n / 2. Weź wartości 0, potem m, potem 1, potem m + 1, potem 2, potem m + 2 i tak dalej. O ile nie masz więcej niż połowy tych samych liczb, nigdy nie otrzymasz równoważnych wartości w kolejności.

Proszę wybacz moją odpowiedź w stylu „ja też”, ale czy odpowiedź Coady nie mogłaby być uproszczona do tego?

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

def srgerg(data):
    heap = [(-freq+1, value) for value, freq in Counter(data).items()]
    heapify(heap)

    freq = 0
    while heap:
        freq, val = heapreplace(heap, (freq+1, val)) if freq else heappop(heap)
        yield val
    yield from repeat(val, -freq)

Edycja: Oto wersja Pythona 2, która zwraca listę:

def srgergpy2(data):
    heap = [(-freq+1, value) for value, freq in Counter(data).items()]
    heapify(heap)

    freq = 0
    result = list()
    while heap:
        freq, val = heapreplace(heap, (freq+1, val)) if freq else heappop(heap)
        result.append(val)
    result.extend(repeat(val, -freq))
    return result

1. Policz, ile razy pojawia się każda wartość
2. Wybierz wartości w kolejności od najczęstszych do najmniej częstych
3. Dodaj wybraną wartość do końcowego wyniku, zwiększając indeks o 2 za każdym razem
4. Zresetuj indeks do 1, jeśli indeks jest poza zakresem

from heapq import heapify, heappop
def distribute(values):
    counts = defaultdict(int)
    for value in values:
        counts[value] += 1
    counts = [(-count, key) for key, count in counts.iteritems()]
    heapify(counts)
    index = 0
    length = len(values)
    distributed = [None] * length
    while counts:
        count, value = heappop(counts)
        for _ in xrange(-count):
            distributed[index] = value
            index = index + 2 if index + 2 < length else 1
    return distributed