Menghasilkan semua permutasi daftar tanpa elemen sama yang berdekatan

Saat kami mengurutkan daftar, seperti

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

elemen yang sama selalu berdekatan dalam daftar yang dihasilkan.

Bagaimana saya bisa mencapai tugas yang berlawanan - mengocok daftar sehingga elemen yang sama tidak pernah (atau jarang mungkin) berdekatan?

Misalnya, untuk daftar di atas, salah satu solusi yang mungkin adalah

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

Secara lebih formal, jika diberi daftar a, buat permutasi pyang meminimalkan jumlah pasangan p[i]==p[i+1].

Karena daftarnya besar, membuat dan memfilter semua permutasi bukanlah suatu pilihan.

Pertanyaan bonus: bagaimana cara menghasilkan semua permutasi seperti itu secara efisien?

Ini adalah kode yang saya gunakan untuk menguji solusi: https://gist.github.com/gebrkn/9f550094b3d24a35aebd

UPD: Memilih pemenang di sini adalah pilihan yang sulit, karena banyak orang memberikan jawaban yang sangat bagus. @VincentvanderWeele , @David Eisenstat , @Coady , @ enrico.bacis, dan @srgerg menyediakan fungsi yang menghasilkan permutasi terbaik dengan sempurna. @tobias_k dan David juga menjawab pertanyaan bonus (buat semua permutasi). Poin tambahan untuk David untuk bukti kebenaran.

Kode dari @VincentvanderWeele tampaknya yang tercepat.

Ini sejalan dengan pseudocode Thijser yang saat ini tidak lengkap. Idenya adalah untuk mengambil jenis barang yang tersisa paling sering kecuali itu baru saja diambil. (Lihat juga implementasi Coady dari algoritma ini.)

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

Bukti kebenaran

Untuk dua jenis item, dengan jumlah k1 dan k2, solusi optimal memiliki cacat k2 - k1 - 1 jika k1 <k2, 0 cacat jika k1 = k2, dan k1 - k2 - 1 cacat jika k1> k2. Kasus = sudah jelas. Yang lainnya simetris; setiap kemunculan elemen minoritas mencegah paling banyak dua cacat dari total k1 + k2 - 1 kemungkinan.

Algoritme rakus ini mengembalikan solusi optimal, dengan logika berikut. Kami menyebut awalan (solusi parsial) aman jika diperluas ke solusi optimal. Jelas awalan kosong itu aman, dan jika awalan aman adalah solusi lengkap maka solusi itu optimal. Sudah cukup untuk menunjukkan secara induktif bahwa setiap langkah serakah menjaga keamanan.

Satu-satunya cara langkah serakah menyebabkan cacat adalah jika hanya satu jenis barang yang tersisa, dalam hal ini hanya ada satu cara untuk melanjutkan, dan cara itu aman. Jika tidak, biarkan P menjadi awalan (aman) sebelum langkah yang dipertimbangkan, biarkan P 'menjadi awalan tepat setelahnya, dan biarkan S menjadi solusi optimal yang memperluas P. Jika S juga memperpanjang P', maka kita selesai. Jika tidak, misalkan P '= Px dan S = PQ dan Q = yQ', dimana x dan y adalah item dan Q dan Q 'adalah barisan.

Misalkan dulu P tidak diakhiri dengan y. Berdasarkan pilihan algoritme, x setidaknya sama seringnya di Q dengan y. Pertimbangkan substring maksimal Q yang hanya berisi x dan y. Jika substring pertama memiliki sedikitnya x sebanyak y, maka substring tersebut dapat ditulis ulang tanpa menimbulkan cacat tambahan diawali dengan x. Jika substring pertama memiliki lebih banyak y daripada x, maka beberapa substring lain memiliki lebih banyak x daripada y, dan kita dapat menulis ulang substring ini tanpa cacat tambahan sehingga x menjadi yang pertama. Dalam kedua kasus tersebut, kami menemukan solusi optimal T yang memperluas P ', sesuai kebutuhan.

Misalkan sekarang P diakhiri dengan y. Ubah Q dengan memindahkan kemunculan pertama x ke depan. Dalam melakukannya, kami memperkenalkan paling banyak satu cacat (di mana x dulu) dan menghilangkan satu cacat (yy).

Menghasilkan semua solusi

Ini adalah jawaban tobias_k ditambah tes yang efisien untuk mendeteksi ketika pilihan yang saat ini sedang dipertimbangkan dibatasi secara global dalam beberapa cara. Waktu berjalan asimtotik adalah optimal, karena overhead pembangkitan berada pada urutan panjang keluaran. Sayangnya, penundaan kasus terburuk adalah kuadrat; dapat direduksi menjadi linier (optimal) dengan struktur data yang lebih baik.

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))])

Pseudocode:

1. Urutkan daftar
2. Ulangi paruh pertama daftar yang diurutkan dan isi semua indeks genap dari daftar hasil
3. Ulangi paruh kedua daftar yang diurutkan dan isi semua indeks ganjil dari daftar hasil

Anda hanya akan memiliki p[i]==p[i+1]jika lebih dari separuh masukan terdiri dari elemen yang sama, dalam hal ini tidak ada pilihan lain selain meletakkan elemen yang sama di tempat yang berurutan (dengan prinsip lubang pidgeon).

Seperti yang ditunjukkan dalam komentar, pendekatan ini mungkin memiliki satu konflik terlalu banyak jika salah satu elemen terjadi setidaknya n/2kali (atau n/2+1untuk ganjil n; ini menggeneralisasi untuk(n+1)/2) untuk genap dan ganjil). Ada paling banyak dua elemen seperti itu dan jika ada dua, algoritme berfungsi dengan baik. Satu-satunya kasus yang bermasalah adalah ketika ada satu elemen yang terjadi setidaknya separuh waktu. Kita dapat dengan mudah menyelesaikan masalah ini dengan mencari elemennya dan mengatasinya terlebih dahulu.

Saya tidak cukup tahu tentang python untuk menulis ini dengan benar, jadi saya mengambil kebebasan untuk menyalin implementasi OP versi sebelumnya dari 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

Algoritme yang telah diberikan untuk mengambil item paling umum yang tersisa yang bukan item sebelumnya benar. Berikut adalah implementasi sederhana, yang secara optimal menggunakan heap untuk melacak yang paling umum.

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]

Anda dapat membuat semua permutasi 'yang tidak diurutkan dengan sempurna' (yang tidak memiliki dua elemen yang sama di posisi yang berdekatan) menggunakan algoritme pelacakan mundur rekursif. Faktanya, satu-satunya perbedaan untuk menghasilkan semua permutasi adalah Anda melacak angka terakhir dan mengecualikan beberapa solusi yang sesuai:

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 []

Perhatikan bahwa dalam formulir ini fungsinya tidak terlalu efisien, karena ia membuat banyak sub-daftar. Selain itu, kami dapat mempercepatnya dengan melihat angka yang paling terbatas terlebih dahulu (angka dengan jumlah tertinggi). Ini adalah versi yang jauh lebih efisien hanya dengan countsmenggunakan nomor.

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

Anda dapat menggunakan ini untuk menghasilkan nextpermutasi yang sempurna, atau listmenahan semuanya. Tapi catatan, bahwa jika tidak ada permutasi sempurna disortir, maka generator ini akan akibatnya menghasilkan tidak ada hasil.

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

Untuk menghindari masalah ini, Anda dapat menggunakan ini bersama dengan salah satu algoritme yang diusulkan di jawaban lain sebagai fallback. Ini akan menjamin untuk mengembalikan permutasi yang tidak diurutkan dengan sempurna, jika ada, atau perkiraan yang baik sebaliknya.

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

Dengan python Anda bisa melakukan hal berikut.

Pertimbangkan Anda memiliki daftar yang diurutkan l, Anda dapat melakukan:

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]

Ini hanya di tempat operasi dan karenanya harus lebih cepat ( O(N)). Perhatikan bahwa Anda akan bergeser dari l[i] == l[i+1]ke l[i] == l[i+2]sehingga urutan yang Anda hasilkan tidak lain adalah acak, tetapi dari cara saya memahami pertanyaan itu, bukan keacakan yang Anda cari.

Idenya adalah untuk membagi daftar yang diurutkan di tengah kemudian menukar setiap elemen lainnya di dua bagian.

Untuk l= [1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5]ini mengarah kel = [3, 1, 4, 2, 5, 1, 3, 1, 4, 2, 5]

Metode ini gagal menyingkirkan semua l[i] == l[i + 1]segera setelah kelimpahan satu unsur lebih besar atau sama dengan setengah dari panjang daftar.

Meskipun cara di atas berfungsi dengan baik selama kelimpahan elemen yang paling sering lebih kecil dari setengah ukuran list, fungsi berikut juga menangani kasus batas (masalah off-by-one yang terkenal) di mana setiap elemen lain dimulai dengan yang pertama harus yang paling melimpah:

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

Ini algoritma yang bagus:

1. Pertama-tama hitung untuk semua angka seberapa sering mereka muncul. Tempatkan jawabannya di peta.

2. Urutkan peta ini sehingga angka yang muncul paling sering muncul lebih dulu.

3. Angka pertama dari jawaban Anda adalah angka pertama di peta yang diurutkan.

4. Gunakan peta dengan yang pertama sekarang menjadi yang lebih kecil.

Jika Anda ingin meningkatkan efisiensi, carilah cara untuk meningkatkan efisiensi langkah penyortiran.

Sebagai jawaban atas pertanyaan bonus: ini adalah algoritma yang menemukan semua permutasi dari suatu himpunan di mana tidak ada elemen yang berdekatan dapat identik. Saya percaya ini menjadi algoritma yang paling efisien secara konseptual (meskipun yang lain mungkin lebih cepat dalam praktiknya karena mereka menerjemahkan ke dalam kode yang lebih sederhana). Itu tidak menggunakan kekuatan kasar, itu hanya menghasilkan permutasi unik, dan jalur yang tidak mengarah ke solusi terputus sejak awal.

Saya akan menggunakan istilah "kelimpahan" untuk unsur dalam himpunan yang terjadi lebih sering daripada semua unsur lain yang digabungkan, dan istilah "kelimpahan" untuk jumlah unsur melimpah dikurangi jumlah unsur lainnya.
misalnya himpunan abactidak memiliki unsur berkelimpahan, himpunan abacadan aabcaamemiliki aunsur melimpah, dan kelimpahan 1 dan 2 masing-masing.

1. Mulailah dengan satu set seperti:

aaabbcd

2. Pisahkan kejadian pertama dari pengulangan:

pertama: abcd
mengulangi: aab

3. Temukan unsur melimpah dalam pengulangan, jika ada, dan hitung kelimpahannya:

kelimpahan unsur:
kelimpahan: 1

4. Hasilkan semua permutasi dari yang pertama di mana jumlah elemen setelah kelimpahan tidak kurang dari kelimpahan: (jadi dalam contoh "a" tidak bisa terakhir)

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. Untuk setiap permutasi, masukkan sekumpulan karakter berulang satu per satu, mengikuti aturan berikut:

5.1. Jika kelimpahan himpunan lebih besar dari jumlah unsur setelah kemunculan terakhir unsur kelimpahan pada permutasi sejauh ini, lanjutkan ke permutasi berikutnya.
Misalnya ketika permutasi sejauh ini abc, himpunan dengan elemen melimpah ahanya dapat disisipkan jika kelimpahannya 2 atau kurang, jadi aaaabcoke, aaaaabctidak.

5.2. Pilih elemen dari set yang kemunculan terakhirnya di permutasi datang lebih dulu.
misalnya ketika permutasi sejauh ini abcbadan set adalah ab, pilihb

5.3. Masukkan elemen yang dipilih setidaknya 2 posisi di sebelah kanan kejadian terakhirnya di permutasi.
misalnya saat menyisipkan bke permutasi babca, hasilnya adalah babcbadanbabcab

5.4. Ulangi langkah 5 dengan setiap permutasi yang dihasilkan dan set lainnya.

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    -

Algoritma ini menghasilkan permutasi yang unik. Jika Anda ingin mengetahui jumlah permutasi (di mana abadihitung dua kali karena Anda dapat mengganti a), kalikan jumlah permutasi unik dengan faktor:

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

di mana N adalah jumlah kemunculan setiap elemen dalam himpunan. Untuk satu setabcdabcaba ini akan menjadi 4! * 3! * 2! * 1! atau 288, yang menunjukkan betapa tidak efisiennya suatu algoritme yang menghasilkan semua permutasi, bukan hanya permutasi unik. Untuk mendaftar semua permutasi dalam kasus ini, cukup daftarkan permutasi unik sebanyak 288 kali :-)

Di bawah ini adalah implementasi (agak kikuk) dalam Javascript; Saya curiga bahasa seperti Python mungkin lebih cocok untuk hal semacam ini. Jalankan potongan kode untuk menghitung permutasi terpisah dari "abracadabra".

// 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"]);

Idenya adalah untuk mengurutkan elemen dari yang paling umum ke yang paling umum, mengambil yang paling umum, mengurangi jumlahnya dan memasukkannya kembali ke dalam daftar dengan menjaga urutan menurun (tetapi hindari meletakkan elemen yang terakhir digunakan terlebih dahulu untuk mencegah pengulangan jika memungkinkan) .

Ini dapat diimplementasikan dengan menggunakan Counterdan 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

Contoh

>>> 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. Urutkan daftar.
2. Buat daftar " pengacakan terbaik" menggunakan algoritme ini

Ini akan memberikan minimum item dari daftar di tempat aslinya (berdasarkan nilai item) sehingga akan mencoba, misalnya Anda, untuk menempatkan 1, 2, dan 3 dari posisi yang diurutkan.

Mulailah dengan daftar panjang n yang diurutkan. Misalkan m = n / 2. Ambil nilai pada 0, lalu m, lalu 1, lalu m + 1, lalu 2, lalu m + 2, dan seterusnya. Kecuali jika Anda memiliki lebih dari setengah angka yang sama, Anda tidak akan pernah mendapatkan nilai yang setara dalam urutan yang berurutan.

Mohon maafkan jawaban gaya "saya juga" saya, tetapi tidak bisakah jawaban Coady disederhanakan menjadi ini?

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)

Edit: Ini adalah versi python 2 yang mengembalikan daftar:

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. Hitung berapa kali setiap nilai muncul
2. Pilih nilai secara berurutan dari yang paling sering hingga yang paling jarang
3. Tambahkan nilai yang dipilih ke hasil akhir, tambahkan indeks sebanyak 2 setiap kali
4. Setel ulang indeks ke 1 jika indeks di luar batas

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