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))])
[1, 2, 1, 3, 1, 4, 1, 5]jest dokładnie takie samo jak[1, 3, 1, 2, 1, 4, 1, 5]według twojego kryterium?