Biz bir liste sıralama, gibi

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

eşit elemanları her zaman sonuç listesi bitişik.

Nasıl ters görev - eşit elemanları hiç (veya olabildiğince nadiren) bitişik olan listeyi karıştırmak elde edebilirsiniz?

Yukarıdaki liste için, örneğin, mümkün çözümlerden biridir

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

Daha biçimsel olarak, a, permütasyon üretmek listesi verilen çift sayısı en aza indiren o p p[i]==p[i 1].

Listeleri büyük olduğundan, ve tüm permütasyon üreten süzme bir seçenek değil.

Tüm bu permütasyon oluşturmak için verimli nasıl? Bonus soru:

Bu çözümleri test etmek için kullanıyorum kodu: https://gist.github.com/gebrkn/9f550094b3d24a35aebd

UDP: birçok kişi mükemmel cevaplar gönderildi çünkü burada zor bir seçim oldu kazanan Seçimi, . *, , *, *15@David Eisenstat*14@Heuster @srgerg mümkün olan en iyi kusursuz permütasyon oluşturma işlevleri sağladı. @tobias_k ve David de bonus soru (permütasyon oluşturmak) cevap verdi. Doğruluğunu ispat için David için ek puan.

@Kod Heuster hızlı görünüyor.

Bu Thijser hatları şu anda eksik ve kesinliği yok. Sadece fikir çekilmiş sürece kalan öğe türlerinin en sık almaktır. (Ayrıca bu algoritma Coady's implementation bakın.)

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

Doğruluğu kanıtı

İki öğesi türleri, sayıları k1, k2, en iyi çözüm vardır k2 - k1 - 1 k1 kusur varsa < k2, 0 kusur varsa, k1 = k2 ve k1 - k2 - 1 kusurları varsa k1 >k2. = Durum ortada. Diğerleri simetrik; azınlık elementin her örneği en fazla k1, k2 - 1 toplam Olası iki kusurları önler.

Bu açgözlü algoritma optimal çözümler, aşağıdaki mantık ile döner. Bir önek (kısmi çözüm) diyoruzgüvenlieğer optimal bir çözüm sunuyor. Açıkça boş önek güvenli ve güvenli bir önek bütün bir çözüm ise bu çözüm en uygunudur. Her açgözlü adım güvenlik korur indüktif göstermek için yeterlidir.

Açgözlü bir adım bir kusur tanıtan tek yolu ise, bu durumda devam etmek için tek bir yolu var, yalnızca bir öğe türü kalır, ve böylece güvenli. Aksi halde, izin P (güvende) önek önce adım altında göz, izin P "öneki hemen sonra, ve izin vermiş olması iyi bir çözüm uzanan P. S genişletir P' de, o zaman işimiz bitti. Aksi takdirde, P' = Px ve S = görüntü kalitesini ve Q =', x ve y çıkarıldığı yer ve Q ve Q' dizileri. yQ izin

P y ile bitmez ilk sanırım. Algoritma seçimi, x en az olarak sık S y gibi. Q maksimal nedenle sadece x ve y içeren düşünün. Eğer ilk dize en az sayıda varsa y olarak x, ek kusur x ile başlamak tanıtan olmadan yeniden olabilir. Eğer ilk dize daha y eğer x, daha sonra başka bir dize daha y x olduğundan, x ilk gider de bazı kusurları olmadan bu dizeleri yeniden yazacağız. Her iki durumda da, P genişleten en uygun çözüm bir T' gerektiği gibi.

P y ile bitiyor varsayın. Ön x ilk geçtiği taşıyarak Q değiştirin. Bunu yaparken, biz en fazla bir kusur x kullanıldığı için () tanıtmak ve bir kusur (yy) ortadan kaldırmak.

Üreten tüm çözümler

Bu şu anda göz altında seçim genel bir şekilde kısıtlı olduğunda algılamak için tobias_k's answer artı verimli testler. Asimptotik süre nesil havai çıkış uzunluğu sipariş olduğu için en uygun olduğunu. Daha iyi veri yapıları ile gecikme ne yazık ki ikinci dereceden; doğrusal azaltılmış olabilir, en kötü durumda (en iyi).

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