Generieren Sie alle Permutationen einer Liste ohne benachbarte gleiche Elemente

87

Wenn wir eine Liste sortieren, wie

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

Gleiche Elemente sind in der resultierenden Liste immer benachbart.

Wie kann ich die entgegengesetzte Aufgabe erreichen - die Liste so mischen, dass gleiche Elemente niemals (oder so selten wie möglich) benachbart sind?

Für die obige Liste ist beispielsweise eine der möglichen Lösungen

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

Wenn eine Liste gegeben ist a, generieren Sie formeller eine Permutation pdavon, die die Anzahl der Paare minimiert p[i]==p[i+1].

Da die Listen groß sind, ist das Generieren und Filtern aller Permutationen keine Option.

Bonusfrage: Wie lassen sich all diese Permutationen effizient generieren?

Dies ist der Code, mit dem ich die Lösungen teste : https://gist.github.com/gebrkn/9f550094b3d24a35aebd

UPD: Die Auswahl eines Gewinners hier war eine schwierige Entscheidung, da viele Leute hervorragende Antworten gepostet haben. @VincentvanderWeele , @David Eisenstat , @Coady , @ enrico.bacis und @srgerg stellten Funktionen bereit, die fehlerfrei die bestmögliche Permutation erzeugen. @tobias_k und David beantworteten auch die Bonusfrage (generiere alle Permutationen). Zusätzliche Punkte an David für den Korrektheitsnachweis.

Der Code von @VincentvanderWeele scheint der schnellste zu sein.

georg
quelle
1
Sie kümmern sich also nur um Gleichheit ? so etwas [1, 2, 1, 3, 1, 4, 1, 5]ist genau das gleiche wie [1, 3, 1, 2, 1, 4, 1, 5]nach deinem kriterium?
Bakuriu
1
Es kann keinen "effizienten" Algorithmus geben. Nehmen Sie eine Liste wie [1, 1, 1, ..., 2, 3, 4, ..., N]mit 2NElementen. Sie können eine Zahl n > 1zwischen jedes aufeinanderfolgende Paar setzen 1, um eine gute Permutation zu erhalten. Dann permutieren Sie die N/2Elemente und erhalten alle gültigen Permutationen (was bedeutet, dass keine schlecht ist, aber es kann mehr geben). Die Anzahl solcher Permutationen ist O (N ^ 2), daher können Sie es nicht besser machen als O (N ^ 2). Immer noch besser als O (N ^ 3) des naiven Ansatzes.
Bakuriu
6
@ Bakuriu: Zwei Dinge: (1) Um klar zu sein, Ihr Beispiel zeigt, dass es keinen effizienten Algorithmus für die Bonusfrage geben kann . (2) Alle optimalen Lösungen für Ihr Beispiel
aufzulisten
11
@msw: Ich mache eine Website und es gibt eine Zeile mit Anzeigenblöcken von verschiedenen Anbietern. Ich möchte sie so anordnen, dass keine Blöcke desselben Anbieters nebeneinander stehen.
Georg
2
Ich würde nicht sagen, dass dies "nicht einmal in der Nähe eines Duplikats" ist, aber das angebliche Duplikat ist eine andere Frage, da der Abstand zwischen identischen Elementen berücksichtigt wird. Personen, die nach dem Kommentar von WhyCry für den Abschluss gestimmt haben: Bitte achten Sie in Zukunft mehr darauf.
David Eisenstat

Antworten:

30

Dies entspricht dem derzeit unvollständigen Pseudocode von Thijser. Die Idee ist, den häufigsten der verbleibenden Artikeltypen zu verwenden, es sei denn, er wurde gerade genommen. (Siehe auch Coadys Implementierung dieses Algorithmus.)

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

Korrektheitsnachweis

Für zwei Elementtypen mit den Zählungen k1 und k2 weist die optimale Lösung k2 - k1 - 1 Fehler auf, wenn k1 <k2, 0 Fehler, wenn k1 = k2, und k1 - k2 - 1 Fehler, wenn k1> k2. Der Fall = ist offensichtlich. Die anderen sind symmetrisch; Jede Instanz des Minderheitselements verhindert höchstens zwei Fehler von insgesamt k1 + k2 - 1 möglich.

Dieser gierige Algorithmus liefert nach der folgenden Logik optimale Lösungen. Wir nennen ein Präfix (Teillösung) sicher, wenn es sich um eine optimale Lösung handelt. Das leere Präfix ist eindeutig sicher, und wenn ein sicheres Präfix eine vollständige Lösung ist, ist diese Lösung optimal. Es genügt, induktiv zu zeigen, dass jeder gierige Schritt die Sicherheit aufrechterhält.

Der einzige Weg, wie ein gieriger Schritt einen Fehler einführt, besteht darin, dass nur noch ein Elementtyp übrig bleibt. In diesem Fall gibt es nur einen Weg, um fortzufahren, und dieser Weg ist sicher. Andernfalls sei P das (sichere) Präfix unmittelbar vor dem betrachteten Schritt, sei P 'das Präfix unmittelbar danach und sei S eine optimale Lösung, die P erweitert. Wenn S auch P' erweitert, sind wir fertig. Andernfalls sei P '= Px und S = PQ und Q = yQ', wobei x und y Elemente und Q und Q 'Sequenzen sind.

Angenommen, P endet nicht mit y. Nach Wahl des Algorithmus ist x in Q mindestens so häufig wie y. Betrachten Sie die maximalen Teilzeichenfolgen von Q, die nur x und y enthalten. Wenn der erste Teilstring mindestens so viele x wie y hat, kann er umgeschrieben werden, ohne zunächst zusätzliche Fehler einzuführen, beginnend mit x. Wenn die erste Teilzeichenfolge mehr y als x hat, hat eine andere Teilzeichenfolge mehr x als y, und wir können diese Teilzeichenfolgen ohne zusätzliche Fehler neu schreiben, sodass x zuerst geht. In beiden Fällen finden wir eine optimale Lösung T, die P 'nach Bedarf erweitert.

Angenommen, P endet jetzt mit y. Ändern Sie Q, indem Sie das erste Vorkommen von x nach vorne verschieben. Dabei führen wir höchstens einen Defekt ein (wo x früher war) und beseitigen einen Defekt (das yy).

Alle Lösungen generieren

Dies ist die Antwort von tobias_k sowie effiziente Tests, um festzustellen, wann die derzeit in Betracht gezogene Auswahl in irgendeiner Weise global eingeschränkt ist. Die asymptotische Laufzeit ist optimal, da der Overhead der Erzeugung in der Größenordnung der Länge der Ausgabe liegt. Die Verzögerung im schlimmsten Fall ist leider quadratisch; es könnte mit besseren Datenstrukturen auf linear (optimal) reduziert werden.

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))])
David Eisenstat
quelle
23

Pseudocode:

  1. Sortieren Sie die Liste
  2. Durchlaufen Sie die erste Hälfte der sortierten Liste und füllen Sie alle geraden Indizes der Ergebnisliste
  3. Durchlaufen Sie die zweite Hälfte der sortierten Liste und füllen Sie alle ungeraden Indizes der Ergebnisliste

Sie haben nur dann, p[i]==p[i+1]wenn mehr als die Hälfte der Eingabe aus demselben Element besteht. In diesem Fall gibt es keine andere Wahl, als dasselbe Element an aufeinanderfolgenden Stellen zu platzieren (nach dem Pidgeon-Hole-Prinzip).


Wie in den Kommentaren ausgeführt, kann dieser Ansatz einen Konflikt zu viele haben, falls eines der Elemente mindestens n/2einmal auftritt (oder n/2+1für ungerade n; dies gilt (n+1)/2)sowohl für gerade als auch für ungerade). Es gibt höchstens zwei solcher Elemente, und wenn es zwei gibt, funktioniert der Algorithmus einwandfrei. Der einzige problematische Fall ist, wenn es ein Element gibt, das mindestens die Hälfte der Zeit auftritt. Wir können dieses Problem einfach lösen, indem wir das Element finden und es zuerst behandeln.

Ich weiß nicht genug über Python, um dies richtig zu schreiben, daher habe ich mir erlaubt, die Implementierung einer früheren Version von github durch das OP zu kopieren:

# 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
Vincent van der Weele
quelle
Nach meinem Verständnis ist dies das, was @jojo tut - nicht immer optimal.
Georg
10
Dies schlägt entweder für [0, 1, 1]oder fehl [0, 0, 1], je nachdem, ob Sie 0-basierte oder 1-basierte Indizes verwenden.
Flornbeben
@georg In der Tat ist dies der gleiche Ansatz wie in meiner Antwort. (Beachten Sie, dass Heuster vor mir geantwortet hat!). In meinem Code werden jedoch die Schritte 2. und 3. kombiniert, wodurch die Effizienz optimiert wird.
Jojo
3
@flornquake Guter Fang! Ich fürchte, es ist der gute alte Fehler. Dieser Ansatz ist also nicht optimal, da 1 Konflikt zu viele haben kann.
Vincent van der Weele
1
@ Heuster: Alle Lichter sind grün! "0 Fehler".
Georg
10

Der bereits angegebene Algorithmus zum Aufnehmen des am häufigsten verwendeten Elements, das nicht das vorherige Element ist, ist korrekt. Hier ist eine einfache Implementierung, bei der ein Heap optimal verwendet wird, um die häufigsten zu verfolgen.

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]
A. Coady
quelle
Gutes Beispiel dafür, wie man Algorithmen NICHT in Python schreibt. Es ist einfach, benötigt aber 30 Minuten, um die Syntax zu verarbeiten.
Alex904
8

Mit einem rekursiven Backtracking-Algorithmus können Sie alle 'perfekt unsortierten' Permutationen (die keine zwei gleichen Elemente an benachbarten Positionen haben) generieren . Der einzige Unterschied zum Generieren aller Permutationen besteht darin, dass Sie die letzte Zahl verfolgen und einige Lösungen entsprechend ausschließen:

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

Beachten Sie, dass die Funktion in dieser Form nicht sehr effizient ist, da sie viele Unterlisten erstellt. Wir können es auch beschleunigen, indem wir zuerst die am stärksten eingeschränkten Zahlen betrachten (diejenigen mit der höchsten Anzahl). Hier ist eine viel effizientere Version, bei der nur countsdie Zahlen verwendet werden.

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

Sie können dies verwenden, um nur die nextperfekte Permutation zu generieren oder listum alle zu halten. Beachten Sie jedoch, dass dieser Generator keine Ergebnisse liefert , wenn keine perfekt unsortierte Permutation vorliegt .

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

Um dieses Problem zu umgehen, können Sie dies zusammen mit einem der in den anderen Antworten vorgeschlagenen Algorithmen als Fallback verwenden. Dies garantiert, dass eine perfekt unsortierte Permutation zurückgegeben wird, falls es eine gibt, oder eine gute Annäherung, falls nicht.

def unsort_safe(lst):
    try:
        return next(unsort_generator(lst))
    except StopIteration:
        return unsort_fallback(lst)
tobias_k
quelle
Dies verwendet O (N ^ 2) Speicher ... für jedes Element in der Permutation, für die Sie eine Kopie der Liste für den rekursiven Aufruf erstellen. Da es rekursiv ist, schlägt es auch mit "kleinen" Längen fehl.
Bakuriu
@ Bakuriu Einverstanden, das habe ich mit "nicht auf Effizienz optimiert" gemeint ... obwohl ich zugeben muss, dass ich O (n ^ 2) nicht ausgenommen habe, aber Sie haben Recht ... Ich werde versuchen, es zu verbessern .
tobias_k
O (N ^ 2) ist immer hinter dem Rücken, wenn Sie eine Rekursion wie haben T(n+1) = something + T(n).
Bakuriu
@tobias_k: Könntest du eine Funktion für nur eine Dauerwelle zum Testen posten?
Georg
@georg Sicher: next(unsort2(collections.Counter(a)));-) Aber da dieses Algo alle Möglichkeiten generiert, warum nicht alle überprüfen? Es sind nur 38 für diese 7-elementige Testliste.
tobias_k
5

In Python können Sie Folgendes tun.

Angenommen, Sie haben eine sortierte Liste l, können Sie Folgendes tun:

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]

Diese sind nur an Ort und Stelle und sollten daher ziemlich schnell sein ( O(N)). Beachten Sie, dass Sie von l[i] == l[i+1]nach wechseln , l[i] == l[i+2]sodass die Reihenfolge, in der Sie enden, alles andere als zufällig ist, aber nach meinem Verständnis der Frage ist es keine Zufälligkeit, nach der Sie suchen.

Die Idee ist, die sortierte Liste in der Mitte aufzuteilen und dann jedes andere Element in den beiden Teilen auszutauschen.

Denn l= [1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5]das führt zul = [3, 1, 4, 2, 5, 1, 3, 1, 4, 2, 5]

Die Methode kann nicht alle l[i] == l[i + 1]Elemente entfernen, sobald die Häufigkeit eines Elements größer oder gleich der Hälfte der Länge der Liste ist.

Während das oben Genannte gut funktioniert, solange die Häufigkeit des häufigsten Elements kleiner als die Hälfte der Größe der Liste ist, behandelt die folgende Funktion auch die Grenzfälle (das berühmte Off-by-One-Problem), bei denen jedes andere Element mit dem beginnt Der erste muss der am häufigsten vorkommende sein:

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
Jojo
quelle
Vielen Dank! Dies schlägt fehl für [3, 2, 1, 2, 1, 3, 2](Rückkehr [2, 1, 3, 1, 2, 2, 3]sollte sein (3, 2, 1, 2, 1, 3, 2)) - das Wesentliche sehen
georg
@georg sorry, mein schlechtes ich habe a vergessen +1. Versuchen Sie es jetzt noch einmal.
Jojo
Immer noch Probleme, [1, 3, 3, 3, 3, 1, 1]=>[3, 1, 3, 3, 1, 3, 1]
georg
@georg, wie ich bereits erwähnt habe, funktioniert es, solange die am häufigsten vorkommende weniger als die Hälfte der Länge der Liste vorhanden ist, was in diesem Beispiel nicht der Fall ist.
Jojo
@georg Also habe ich das Teil hinzugefügt, das den of-by-one-Fehler behandelt. Dieser Teil ist nicht besonders schnell (ungefähr der gleiche wie der von Thijser vorgeschlagene Algorithmus), obwohl er nur in seltenen Fällen ausgeführt wird.
Jojo
5

Hier ist ein guter Algorithmus:

  1. Zählen Sie zunächst für alle Zahlen, wie oft sie vorkommen. Platziere die Antwort in einer Karte.

  2. Sortieren Sie diese Karte so, dass die am häufigsten vorkommenden Zahlen an erster Stelle stehen.

  3. Die erste Nummer Ihrer Antwort ist die erste Nummer in der sortierten Karte.

  4. Resortieren Sie die Karte, wobei die erste jetzt eine kleinere ist.

Wenn Sie die Effizienz verbessern möchten, suchen Sie nach Möglichkeiten, um die Effizienz des Sortierschritts zu steigern.

Thijser
quelle
Ja, das hat @tobias_k getan. Scheint gut zu funktionieren!
Georg
@georg Es ist ein bisschen anders ... Ich benutze den Zähler nur, um die Platzkomplexität zu reduzieren, aber ich teste die Zahlen nicht in einer bestimmten Reihenfolge (dachte, dies könnte eine weitere Beschleunigung sein). Was anders ist, ist, dass meine Lösung immer alle 'perfekten' Permutationen liefert, wenn überhaupt , während dies die beste (?) Lösung ergeben sollte (perfekt oder nicht).
tobias_k
3
Dieser Pseudocode ist nicht ganz richtig; Wenn die Anzahl der Elemente 5 x, 2 y, 2 z beträgt, werden unnötigerweise x zusammengesetzt. Siehe meine Antwort für eine Lösung.
David Eisenstat
1
Einverstanden. Für zB [1,1,1,2,3] ergibt dies zB [1,1,2,1,3] anstelle von [1,2,1,3,1].
tobias_k
Schritt 3 ist tatsächlich kontraproduktiv. Wenn eine Nummer gemeinsam ist (mindestens zwei Einträge mehr als die nächsthäufigste Nummer), wird diese Nummer in Schritt 3 ohne Begründung zweimal hintereinander verwendet.
MSalters
5

Antwort auf die Bonusfrage: Dies ist ein Algorithmus, der alle Permutationen einer Menge findet, bei denen keine benachbarten Elemente identisch sein können. Ich glaube, dass dies konzeptionell der effizienteste Algorithmus ist (obwohl andere in der Praxis möglicherweise schneller sind, weil sie in einfacheren Code übersetzt werden). Es verwendet keine rohe Gewalt, es erzeugt nur eindeutige Permutationen, und Pfade, die nicht zu Lösungen führen, werden zum frühesten Zeitpunkt abgeschnitten.

Ich werde den Begriff "reichlich vorhandenes Element" für ein Element in einer Menge verwenden, das häufiger vorkommt als alle anderen Elemente zusammen, und den Begriff "Fülle" für die Anzahl der reichlich vorhandenen Elemente abzüglich der Anzahl anderer Elemente.
zB hat die Menge abackein reichlich vorhandenes Element, die Mengen abacaund aabcaahaben aals reichlich vorhandenes Element und Fülle 1 bzw. 2.

  1. Beginnen Sie mit einem Set wie:

aaabbcd

  1. Trennen Sie die ersten Vorkommen von den Wiederholungen:

firsts: abcd
wiederholt: aab

  1. Finden Sie das reichlich vorhandene Element in den Wiederholungen, falls vorhanden, und berechnen Sie die Häufigkeit:

reichlich vorhandenes Element: eine
Fülle: 1

  1. Generieren Sie alle Permutationen der ersten, bei denen die Anzahl der Elemente nach dem reichlich vorhandenen Element nicht geringer ist als die Häufigkeit: (im Beispiel kann das "a" nicht das letzte sein)

abcd, abdc, acbd, acdb, adbc, adcb, bacd, badc, bcad, bcda , bdac, bdca ,
cabd, cadb, cbad, cbda , cdab, cdba , dabc, dacb, abac, dbca , dcab, dcba

  1. Fügen Sie für jede Permutation den Satz wiederholter Zeichen nacheinander ein und befolgen Sie dabei die folgenden Regeln:

5.1. Wenn die Häufigkeit der Menge größer ist als die Anzahl der Elemente nach dem letzten Auftreten des häufig vorkommenden Elements in der Permutation, fahren Sie mit der nächsten Permutation fort.
zB wenn die Permutation so weit ist abc, kann eine Menge mit reichlich vorhandenem Element anur eingefügt werden, wenn die Häufigkeit 2 oder weniger aaaabcbeträgt , also ist es in Ordnung, aaaaabcnicht wahr?

5.2. Wählen Sie das Element aus der Menge aus, dessen letztes Vorkommen in der Permutation an erster Stelle steht.
zB wenn die Permutation so weit ist abcbaund eingestellt ist ab, wählen Sieb

5.3. Fügen Sie das ausgewählte Element mindestens 2 Positionen rechts von seinem letzten Vorkommen in der Permutation ein.
zB beim Einfügen bin die Permutation babcasind die Ergebnisse babcbaundbabcab

5.4. Wiederholen Sie Schritt 5 mit jeder resultierenden Permutation und dem Rest des Satzes.

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    -

Dieser Algorithmus erzeugt eindeutige Permutationen. Wenn Sie die Gesamtzahl der Permutationen wissen möchten (wobei abazweimal gezählt wird, weil Sie die a-Werte wechseln können), multiplizieren Sie die Anzahl der eindeutigen Permutationen mit einem Faktor:

F = N 1 ! * N 2 ! * ... * N n !

Dabei ist N die Anzahl der Vorkommen jedes Elements in der Menge. Für einen Satz abcdabcabawäre dies 4! * 3! * 2! * 1! oder 288, was zeigt, wie ineffizient ein Algorithmus ist, der alle Permutationen anstelle nur der eindeutigen generiert. Um in diesem Fall alle Permutationen aufzulisten, listen Sie einfach die eindeutigen Permutationen 288 Mal auf :-)

Unten finden Sie eine (ziemlich ungeschickte) Implementierung in Javascript. Ich vermute, dass eine Sprache wie Python für solche Dinge besser geeignet ist. Führen Sie das Code-Snippet aus, um die getrennten Permutationen von "Abrakadabra" zu berechnen.

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

m69 '' snarky und unwillkommen ''
quelle
1
Danke dafür! Ich werde sehen, ob dies in Javascript etwas verkürzt werden kann.
stt106
4

Die Idee ist, die Elemente von den häufigsten zu den am wenigsten verbreiteten zu sortieren, die häufigsten zu nehmen, die Anzahl zu verringern und sie wieder in die Liste aufzunehmen, wobei die absteigende Reihenfolge beibehalten wird (wobei jedoch zu vermeiden ist, dass das zuletzt verwendete Element an erster Stelle steht, um Wiederholungen zu vermeiden, wenn dies möglich ist). .

Dies kann implementiert werden mit Counterund 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

Beispiel

>>> 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]
enrico.bacis
quelle
Dies schlägt beispielsweise fehl, [1, 1, 2, 3]wenn es Lösungen gibt, wie z [1, 2, 1, 3].
Bakuriu
Ja, das habe ich gerade gemerkt, sorry
enrico.bacis
Vielen Dank! Dies führt nicht immer zum optimalen Ergebnis, z. B. weil [1, 2, 3, 2, 3, 2, 2]es zurückkehrt [2, 3, 1, 2, 3, 2, 2](1 Fehler), während das Ideal ist (2, 1, 2, 3, 2, 3, 2)) - siehe das Wesentliche.
Georg
@georg Richtig, netter Fang, ich habe es aktualisiert und dabei das einfache Prinzip beibehalten, das es verwendet.
enrico.bacis
@ enrico.bacis: danke! Die neue Version funktioniert einwandfrei. Ich habe das Wesentliche aktualisiert. Schade, dass ich dich nicht mehr unterstützen kann.
Georg
2
  1. Sortieren Sie die Liste.
  2. Generieren Sie mit diesem Algorithmus ein "bestes Shuffle" der Liste

Es wird das Minimum an Elementen aus der Liste an ihrer ursprünglichen Stelle angegeben (nach Elementwert), sodass beispielsweise versucht wird, die Einsen, Zweien und Dreien von ihren sortierten Positionen zu entfernen.

Paddy3118
quelle
Ich habe es versucht best_shuffleund es generiert [1,1,1,2,3] -> [3, 1, 2, 1, 1]- nicht ideal!
Georg
2

Beginnen Sie mit der sortierten Liste der Länge n. Sei m = n / 2. Nehmen Sie die Werte bei 0, dann m, dann 1, dann m + 1, dann 2, dann m + 2 und so weiter. Wenn Sie nicht mehr als die Hälfte der Zahlen gleich haben, erhalten Sie niemals äquivalente Werte in aufeinanderfolgender Reihenfolge.

rchuso
quelle
Danke für die Idee. Ich denke, das hat @Heuster implementiert.
Georg
2

Bitte verzeihen Sie meine Antwort im "Ich auch" -Stil, aber könnte Coadys Antwort darauf nicht vereinfacht werden?

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)

Bearbeiten: Hier ist eine Python 2-Version, die eine Liste zurückgibt:

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
srgerg
quelle
Ja, das scheint gut zu funktionieren (außer dass ich auf py2 bin und die Funktion eine Liste zurückgeben sollte).
Georg
@georg Ok, ich habe eine Python 2-Version hinzugefügt, die eine Liste zurückgibt.
Srgerg
2
  1. Zählen Sie, wie oft jeder Wert angezeigt wird
  2. Wählen Sie die Werte in der Reihenfolge von am häufigsten bis am wenigsten häufig
  3. Fügen Sie der endgültigen Ausgabe den ausgewählten Wert hinzu und erhöhen Sie den Index jedes Mal um 2
  4. Setzen Sie den Index auf 1 zurück, wenn der Index außerhalb der Grenzen liegt
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
Joel
quelle