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 das Gegenteil erreichen - mische die Liste so, dass gleiche Elemente niemals (oder so selten wie möglich) nebeneinander stehen?

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

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

Formeller, eine Liste gegebenaerzeugen eine Permutationp davon, dass die Anzahl der Paare minimiertp[i]==p[i+1].

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

Bonusfrage: Wie können solche Permutationen effizient generiert werden?

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

UPD: Es war eine schwierige Entscheidung, hier einen Gewinner auszuwählen, da viele Leute hervorragende Antworten gaben.@VincentvanderWeele, @ David Eisenstat, @Coady, @ enrico.bacis und@srgerg bereitgestellte Funktionen, die die bestmögliche Permutation einwandfrei erzeugen.@tobias_k und David beantwortete auch die Bonusfrage (generiere alle Permutationen). Zusätzliche Punkte an David für den Korrektheitsnachweis.

Der Code von @VincentvanderWeele scheint der schnellste zu sein.