Generieren Sie alle Permutationen einer Liste ohne benachbarte gleiche Elemente

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.

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

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

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]

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)

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

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.

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

2. Trennen Sie die ersten Vorkommen von den Wiederholungen:

firsts: abcd
wiederholt: aab

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

reichlich vorhandenes Element: eine
Fülle: 1

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

5. 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 ₁ ! * N ₂ ! * ... * 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"]);

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]

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.

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.

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

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