Kiedy sortujemy listę, tak jak

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

Równe elementy są zawsze sąsiadujące na uzyskanej liście.

Jak mogę osiągnąć odwrotną zadanie - przetasuj listę, aby równe elementy nigdy nie są (lub jak najdalej) sąsiednie?

Na przykład, dla powyższej listy jest jeden z możliwych rozwiązań

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

Formalnie, biorąc pod uwagę listę a, wygenerować permutację p, która minimalizuje liczbę par p[i]==p[i+1].

Ponieważ listy są duże, generujące i filtrujące wszystkie permutacje nie jest opcją.

Pytanie bonusowe: Jak skutecznie wygenerować wszystkie takie permutacje?

Jest to kod, którego używam, aby przetestować rozwiązania: https://gist.github.com/gebrkn / 9F550094B3D24A35AEBD.

Updatek: Wybór zwycięzcy tutaj był trudny wybór, ponieważ wielu ludzi opublikowało doskonałe odpowiedzi. @vincentvanderWeele, @david Eisenstat, @Coady, @ Enrico.BACIS i @srgerg Dostarczone funkcje, które generują najlepszą możliwą permukietę. @Tobias_K i David również odpowiedział na pytanie bonusowe (generuj wszystkie permutacje). Dodatkowe punkty do Dawida do odpowiednika poprawności.

Kod z @vincentvanderweele wydaje się być najszybszy.

87
georg 13 sierpień 2014, 16:09

11 odpowiedzi

Najlepsza odpowiedź

Jest to wzdłuż linii obecnie niekompletnego pseudokodu Thijsera. Chodzi o to, aby przyjąć najczęstsze rodzaje pozostałych typów elementów, chyba że zostało to zrobione. (Patrz także Wdrożenie Coady tego algorytmu).

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

W przypadku dwóch typów elementów, z licznikami K1 i K2, optymalny roztwór ma k2 - K1 - 1 wady, jeśli K1 K2. Case jest oczywista. Pozostałe są symetryczne; Każda instancja elementu mniejszościowego zapobiega większości dwóch defektów w sumie K1 + K2 - 1 możliwe.

Ten chciwy algorytm zwraca optymalne rozwiązania, według następującej logiki. Nazywamy prefiksem (roztwór częściowy) sejf , jeśli rozciąga się na optymalne rozwiązanie. Oczywiście pusty prefiks jest bezpieczny, a jeśli bezpieczny prefiks jest cały roztwór, to rozwiązanie jest optymalne. Wystarczy pokazać indukcyjnie, że każdy chciwy krok utrzymuje bezpieczeństwo.

Jedynym sposobem, w jaki chciwy krok wprowadza wadę, jest to, że tylko jeden typ przedmiotu pozostaje, w którym to przypadku jest tylko jeden sposób na kontynuowanie, a ten sposób jest bezpieczny. W przeciwnym razie niech P BE (bezpieczny) prefiks tuż przed rozważanym krokiem, niech P 'będzie prefiksem tuż po tym, jak i pozwolimy być optymalnym rozwiązaniem rozciągającym się P. If s rozszerza p', a następnie skończyliśmy. W przeciwnym razie niech p '= px i s = pq i q = yq', gdzie X i y są przedmiotami, a Q, a Q 'są sekwencjami.

Przypuśćmy najpierw, że p nie kończy się tobą. Według wyboru algorytmu X jest przynajmniej tak często w q jak y. Rozważ maksymalne podciągi Q zawierające tylko X i Y. Jeśli pierwsza substring ma co najmniej tyle X, jak Y, może być przepisana bez wprowadzenia dodatkowych defektów, aby rozpocząć od X. Jeśli pierwsza substring ma więcej Y; W obu przypadkach znajdujemy optymalne rozwiązanie T, które rozciąga się, w razie potrzeby.

Przypuśćmy teraz, że P kończą się Y. Zmodyfikuj q, przesuwając pierwsze wystąpienie X do przodu. W ten sposób przedstawiamy najwyżej jedną wadę (gdzie X kiedy X) i wyeliminować jedną wadę (YY).

Generowanie wszystkich rozwiązań

Jest to Odpowiedź Tobias_K plus wydajne testy do wykrywania, gdy obecnie rozważany jest wybór w jakiś sposób. Asymptotyczny czas pracy jest optymalny, ponieważ narzut generowania jest na kolejności długości wyjścia. Najgorsze opóźnienie niestety jest kwadratowe; Można go zmniejszyć do liniowy (optymalny) 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))])
30
Community 23 maj 2017, 12:25

Pseudo kod:

  1. Sortuj listę
  2. Pętla nad pierwszą połową posortowanej listy i wypełnij wszystkie nawet indeksy listy wyników
  3. Pętla nad drugą połową posortowanej listy i wypełnij wszystkie nieparzyste wskaźniki listy wyników

Będziesz mieć tylko p[i]==p[i+1], jeśli więcej niż połowa wejścia składa się z tego samego elementu, w którym to przypadku nie ma innego wyboru niż wprowadzenie tego samego elementu w kolejnych miejscach (przez zasadę Pidgeon Hole).


Jak wskazano w komentarzach, podejście to może mieć jeden konflikt zbyt wielu na wypadek, gdyby jeden z elementów występuje co najmniej n/2 razy (lub {x1}} dla nieparzystego n; dla tego uogólnia {{x2}; X3}} dla obu i nieparzystych). Jest najwyżej dwa takie elementy, a jeśli są dwa, algorytm działa dobrze. Jedynym problematycznym przypadkiem jest jeden element, który występuje co najmniej połowę czasu. Możemy po prostu rozwiązać ten problem, znajdując element i najpierw się z nim zajmując.

Nie wiem wystarczająco dużo o Pythonie, aby prawidłowo napisać to, więc wziąłem wolność, aby skopiować wdrożenie poprzedniej wersji 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
23
Vincent van der Weele 14 sierpień 2014, 10:34

Algorytm już podany z pobierania najczęstszego przedmiotu pozostawionego, który nie jest poprzedni element, jest poprawny. Oto prosta implementacja, która optymalnie używa sterty 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]
10
A. Coady 13 sierpień 2014, 16:56

Możesz wygenerować wszystkie "doskonale niesorturowane" permutacje (które nie mają dwóch równych elementów w sąsiednich pozycjach) przy użyciu rekurencyjnego algorytmu backtrakingu. W rzeczywistości jedyną różnicą w zakresie generowania wszystkich permutacji jest to, że śledzisz ostatni numer i niektóre rozwiązania odpowiednio:

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

Należy pamiętać, że w tej formie funkcja nie jest bardzo wydajna, ponieważ tworzy dużo podkładów. Ponadto możemy go przyspieszyć, patrząc na najpierw najczęściej ograniczone liczby (te z najwyższą liczbą). Oto znacznie bardziej wydajna wersja przy użyciu tylko numerów counts.

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 generowania idealnej permutacji next lub list posiadania wszystkich. Należy jednak pamiętać, że jeśli jest nr Doskonale nieistniejąca permutacji, to generator zatem zapewni wyniki nr wyniki.

>>> 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 ominąć ten problem, można użyć tego razem z jednym z algorytmów zaproponowanych w innych odpowiedziach jako awarię. Gwarantuje to, aby zwrócić doskonale niesortowaną permutację, jeśli jest jeden lub dobry przybliżenie inaczej.

def unsort_safe(lst):
    try:
        return next(unsort_generator(lst))
    except StopIteration:
        return unsort_fallback(lst)
8
tobias_k 13 sierpień 2014, 18:57

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

Rozważmy, ż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ą one po prostu operacje, a zatem powinny być raczej szybkie (O(N)). Należy pamiętać, że będziesz przesunąć z l[i] == l[i+1] do l[i] == l[i+2], więc kolejność, z którą się skończy, jest cokolwiek innego, ale z tego, jak rozumiem pytanie, że nie jest przypadkowość, której szukasz.

Ideą jest podzielenie posortowanej listy pośrodku, a następnie wymień każdy inny element w dwóch częściach.

Dla l= [1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5] To prowadzi do l = [3, 1, 4, 2, 5, 1, 3, 1, 4, 2, 5]

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

Podczas gdy powyższe działa dobrze, dopóki obfitość najczęstszego elementu jest mniejsza niż połowa wielkości listy, Poniższa funkcja obsługuje również przypadki graniczne (słynny problem OFF-One) gdzie każdy inny element zaczynający się od pierwszego, 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
5
jojo 13 sierpień 2014, 15:47

Oto dobry algorytm:

  1. Przede wszystkim liczyć dla wszystkich numerów, jak często występują. Umieść odpowiedź na mapie.

  2. Sortuj tę mapę, aby najczęściej występują najczęściej liczby.

  3. Pierwsza liczba odpowiedzi jest pierwsza liczba w posortowanej mapie.

  4. Ośrodek mapę z pierwszym, który jest mniejszy.

Jeśli chcesz poprawić wydajność, szukaj sposobów zwiększenia wydajności etapu sortowania.

5
Hugo Dozois 13 sierpień 2014, 18:54

Chodzi o to, aby posortować elementy z najczęstszych do najmniejszej wspólnej, najczęściej obniżyć liczenie i umieścić go z powrotem na liście, utrzymując kolejność malejącą (ale unikanie umieszczania ostatniego elementu używanego, aby zapobiec powtórzeniom, jeśli to możliwe) .

Można to zaimplementować za pomocą Counter i 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]
4
enrico.bacis 20 sierpień 2014, 07:21
  1. Sortuj listę.
  2. Wygeneruj "Best Shuffle" listy za pomocą Ten algorytm

Daje minimalne elementy z listy w ich oryginalnym miejscu (według wartości produktu), więc spróbuje, aby na przykład umieścić 1's, 2's i 3's od ich posortowanych pozycji.

2
Paddy3118 14 sierpień 2014, 08:21

Zacznij od posortowanej listy długości n. Niech m = n / 2. Weź wartości w 0, a następnie m, a następnie 1, a następnie M + 1, a następnie 2, a następnie M + 2 i tak dalej. Chyba że masz więcej niż połowę liczb, nigdy nie otrzymasz równoważnych wartości w kolejnej kolejności.

2
rchuso 19 sierpień 2014, 23:23

Wybacz mi "Me Joe" Style Odpowiedź, ale nie może Odpowiedź Coady jest to uproszczone?

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)

Edytuj: Oto wersja Python 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
2
Community 23 maj 2017, 12:25
  1. liczenie liczby razy każda wartość pojawia się
  2. Wybierz wartości w kolejności od najczęstszych do najmniejszej liczby
  3. Dodaj wybraną wartość do ostatecznego wyjścia, zwiększając indeks o 2 za każdym razem
  4. reset indeks do 1, jeśli indeks poza granicami
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
2
Joel 1 wrzesień 2014, 10:08