Générer toutes les permutations d'une liste sans éléments égaux adjacents

Lorsque nous trions une liste, comme

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

les éléments égaux sont toujours adjacents dans la liste résultante.

Comment puis-je accomplir la tâche opposée - mélanger la liste afin que des éléments égaux ne soient jamais (ou aussi rarement que possible) adjacents?

Par exemple, pour la liste ci-dessus, l'une des solutions possibles est

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

Plus formellement, à partir d'une liste a, générez-en une permutation pqui minimise le nombre de paires p[i]==p[i+1].

Comme les listes sont volumineuses, générer et filtrer toutes les permutations n'est pas une option.

Question bonus: comment générer efficacement toutes ces permutations?

C'est le code que j'utilise pour tester les solutions: https://gist.github.com/gebrkn/9f550094b3d24a35aebd

UPD: Choisir un gagnant ici était un choix difficile, car de nombreuses personnes ont publié d'excellentes réponses. @VincentvanderWeele , @David Eisenstat , @Coady , @ enrico.bacis et @srgerg ont fourni des fonctions qui génèrent parfaitement la meilleure permutation possible. @tobias_k et David ont également répondu à la question bonus (générer toutes les permutations). Points supplémentaires à David pour la preuve d'exactitude.

Le code de @VincentvanderWeele semble être le plus rapide.

Cela va dans le sens du pseudocode actuellement incomplet de Thijser. L'idée est de prendre le plus fréquent des types d'éléments restants, sauf s'il vient d'être pris. (Voir aussi l'implémentation de cet algorithme par 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

Preuve d'exactitude

Pour deux types d'items, avec des comptages k1 et k2, la solution optimale a k2 - k1 - 1 défauts si k1 <k2, 0 défaut si k1 = k2, et k1 - k2 - 1 défauts si k1> k2. Le cas = est évident. Les autres sont symétriques; chaque instance de l'élément minoritaire empêche au plus deux défauts sur un total de k1 + k2 - 1 possible.

Cet algorithme gourmand renvoie des solutions optimales, par la logique suivante. Nous appelons un préfixe (solution partielle) sûr s'il s'étend à une solution optimale. Il est clair que le préfixe vide est sûr, et si un préfixe sûr est une solution complète, cette solution est optimale. Il suffit de montrer de manière inductive que chaque pas gourmand maintient la sécurité.

La seule façon pour une étape gourmande d'introduire un défaut est s'il ne reste qu'un seul type d'élément, auquel cas il n'y a qu'une seule façon de continuer, et cette façon est sûre. Sinon, soit P le préfixe (sûr) juste avant l'étape considérée, soit P 'le préfixe juste après, et soit S une solution optimale étendant P. Si S étend P' aussi, alors c'est fini. Sinon, soit P '= Px et S = PQ et Q = yQ', où x et y sont des éléments et Q et Q 'sont des séquences.

Supposons d'abord que P ne se termine pas par y. Par le choix de l'algorithme, x est au moins aussi fréquent dans Q que y. Considérons les sous-chaînes maximales de Q contenant uniquement x et y. Si la première sous-chaîne a au moins autant de x que de y, elle peut être réécrite sans introduire de défauts supplémentaires pour commencer par x. Si la première sous-chaîne a plus de y que de x, alors une autre sous-chaîne a plus de x que de y, et nous pouvons réécrire ces sous-chaînes sans défauts supplémentaires afin que x passe en premier. Dans les deux cas, on trouve une solution optimale T qui étend P ', selon les besoins.

Supposons maintenant que P finisse par y. Modifiez Q en déplaçant la première occurrence de x vers l'avant. Ce faisant, nous introduisons au plus un défaut (où x était auparavant) et éliminons un défaut (le yy).

Générer toutes les solutions

C'est la réponse de tobias_k plus des tests efficaces pour détecter quand le choix actuellement considéré est globalement contraint d'une manière ou d'une autre. Le temps de fonctionnement asymptotique est optimal, puisque le surcoût de génération est de l'ordre de la longueur de la sortie. Le retard dans le pire des cas est malheureusement quadratique; il pourrait être réduit à linéaire (optimal) avec de meilleures structures de données.

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. Trier la liste
2. Faites une boucle sur la première moitié de la liste triée et remplissez tous les indices pairs de la liste de résultats
3. Boucle sur la seconde moitié de la liste triée et remplit tous les indices impairs de la liste de résultats

Vous ne l'aurez que p[i]==p[i+1]si plus de la moitié de l'entrée est constituée du même élément, auquel cas il n'y a pas d'autre choix que de placer le même élément à des endroits consécutifs (selon le principe du trou pidgeon).

Comme indiqué dans les commentaires, cette approche peut avoir un conflit de trop au cas où l'un des éléments se produirait au moins n/2fois (ou n/2+1pour impair n; cela se généralise à la (n+1)/2)fois pour pair et impair). Il y a au plus deux de ces éléments et s'il y en a deux, l'algorithme fonctionne très bien. Le seul cas problématique est celui où un élément se produit au moins la moitié du temps. Nous pouvons simplement résoudre ce problème en trouvant l'élément et en le traitant en premier.

Je ne connais pas assez python pour écrire cela correctement, alors j'ai pris la liberté de copier l'implémentation de l'OP d'une version précédente de 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

L'algorithme déjà donné de prendre l'élément le plus courant à gauche qui n'est pas l'élément précédent est correct. Voici une implémentation simple, qui utilise de manière optimale un tas pour suivre les plus courantes.

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]

Vous pouvez générer toutes les permutations «parfaitement non triées» (qui n'ont pas deux éléments égaux dans des positions adjacentes) en utilisant un algorithme de retour arrière récursif. En fait, la seule différence pour générer toutes les permutations est que vous gardez une trace du dernier nombre et excluez certaines solutions en conséquence:

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

Notez que sous cette forme la fonction n'est pas très efficace, car elle crée de nombreuses sous-listes. De plus, nous pouvons l'accélérer en examinant d'abord les nombres les plus contraints (ceux qui ont le plus grand nombre). Voici une version beaucoup plus efficace utilisant uniquement countsles chiffres.

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

Vous pouvez l'utiliser pour générer juste la nextpermutation parfaite, ou pour les listmaintenir toutes. Mais notez que s'il n'y a pas de permutation parfaitement non triée, alors ce générateur ne donnera par conséquent aucun résultat.

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

Pour contourner ce problème, vous pouvez l'utiliser avec l'un des algorithmes proposés dans les autres réponses comme solution de secours. Cela garantira de retourner une permutation parfaitement non triée, s'il y en a une, ou une bonne approximation dans le cas contraire.

def unsort_safe(lst):
    try:
        return next(unsort_generator(lst))
    except StopIteration:
        return unsort_fallback(lst)

En python, vous pouvez faire ce qui suit.

Considérez que vous avez une liste triée l, vous pouvez faire:

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]

Ce ne sont que des opérations en place et devraient donc être assez rapides ( O(N)). Notez que vous passerez de l[i] == l[i+1]à l[i] == l[i+2]afin que l'ordre dans lequel vous vous retrouvez soit tout sauf aléatoire, mais d'après ma compréhension de la question, ce n'est pas le hasard que vous recherchez.

L'idée est de diviser la liste triée au milieu puis d'échanger tous les autres éléments dans les deux parties.

Car l= [1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5]cela conduit àl = [3, 1, 4, 2, 5, 1, 3, 1, 4, 2, 5]

La méthode ne parvient pas à se débarrasser de tous les l[i] == l[i + 1]dès que l'abondance d'un élément est supérieure ou égale à la moitié de la longueur de la liste.

Bien que ce qui précède fonctionne bien tant que l'abondance de l'élément le plus fréquent est inférieure à la moitié de la taille de la liste, la fonction suivante gère également les cas limites (le fameux problème off-by-one) où tous les autres éléments commençant par le le premier doit être le plus abondant:

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

Voici un bon algorithme:

1. Tout d'abord, comptez pour tous les nombres la fréquence à laquelle ils se produisent. Placez la réponse sur une carte.

2. trier cette carte de sorte que les nombres les plus fréquents viennent en premier.

3. Le premier chiffre de votre réponse est le premier chiffre de la carte triée.

4. Resort la carte avec le premier étant maintenant un plus petit.

Si vous souhaitez améliorer l'efficacité, recherchez des moyens d'augmenter l'efficacité de l'étape de tri.

En réponse à la question bonus: il s'agit d'un algorithme qui trouve toutes les permutations d'un ensemble où aucun élément adjacent ne peut être identique. Je pense que c'est l'algorithme le plus efficace du point de vue conceptuel (bien que d'autres puissent être plus rapides en pratique car ils se traduisent par un code plus simple). Il n'utilise pas la force brute, il ne génère que des permutations uniques et les chemins ne menant pas à des solutions sont coupés au plus tôt.

J'utiliserai le terme «élément abondant» pour un élément dans un ensemble qui apparaît plus souvent que tous les autres éléments combinés, et le terme «abondance» pour le nombre d'éléments abondants moins le nombre d'autres éléments.
par exemple, l'ensemble abacn'a pas d'élément abondant, les ensembles abacaet aabcaaont acomme élément abondant, et l'abondance 1 et 2 respectivement.

1. Commencez avec un ensemble comme:

aaabbcd

2. Séparez les premières occurrences des répétitions:

premières: abcd
répète: aab

3. Trouvez l'élément abondant dans les répétitions, le cas échéant, et calculez l'abondance:

élément abondant: a
abondance: 1

4. Générer toutes les permutations des premiers où le nombre d'éléments après l'élément abondant n'est pas inférieur à l'abondance: (donc dans l'exemple, le "a" ne peut pas être le dernier)

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. Pour chaque permutation, insérez le jeu de caractères répétés un par un, en suivant ces règles:

5.1. Si l'abondance de l'ensemble est supérieure au nombre d'éléments après la dernière occurrence de l'élément abondant dans la permutation jusqu'à présent, passez à la permutation suivante.
Par exemple, lorsque la permutation est jusqu'à présent abc, un ensemble avec un élément abondant ne apeut être inséré que si l'abondance est de 2 ou moins, donc aaaabcc'est ok, aaaaabcnon.

5.2. Sélectionnez l'élément de l'ensemble dont la dernière occurrence dans la permutation vient en premier.
Par exemple, lorsque la permutation est jusqu'à présent abcbaet définie est ab, sélectionnezb

5.3. Insérez l'élément sélectionné au moins 2 positions à droite de sa dernière occurrence dans la permutation.
par exemple lors de l'insertion bdans la permutation babca, les résultats sontbabcba etbabcab

5.4. Réexécutez l'étape 5 avec chaque permutation résultante et le reste de l'ensemble.

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    -

Cet algorithme génère des permutations uniques. Si vous voulez connaître le nombre total de permutations (oùaba est compté deux fois car vous pouvez changer les a), multipliez le nombre de permutations uniques par un facteur:

F = N ₁ ! * N ₂ ! * ... * N _n !

où N est le nombre d'occurrences de chaque élément de l'ensemble. Pour un ensembleabcdabcaba ce serait 4! * 3! * 2! * 1! ou 288, qui démontre à quel point un algorithme est inefficace qui génère toutes les permutations au lieu de seulement les uniques. Pour lister toutes les permutations dans ce cas, listez simplement les permutations uniques 288 fois :-)

Voici une implémentation (plutôt maladroite) en Javascript; Je soupçonne qu'un langage comme Python peut être mieux adapté à ce genre de choses. Exécutez l'extrait de code pour calculer les permutations séparées de "abracadabra".

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

L'idée est de trier les éléments du plus commun au moins commun, de prendre le plus commun, de diminuer son nombre et de le remettre dans la liste en gardant l'ordre décroissant (mais en évitant de mettre le dernier élément utilisé en premier pour éviter les répétitions lorsque cela est possible) .

Cela peut être implémenté en utilisant Counteret 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

Exemple

>>> 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. Triez la liste.
2. Générer un "meilleur shuffle" de la liste en utilisant cet algorithme

Il donnera le minimum d'éléments de la liste à leur emplacement d'origine (par valeur d'élément) afin qu'il essaie, pour votre exemple, de mettre les 1, 2 et 3 loin de leurs positions triées.

Commencez par la liste triée de longueur n. Soit m = n / 2. Prenez les valeurs à 0, puis m, puis 1, puis m + 1, puis 2, puis m + 2, et ainsi de suite. À moins que vous n'ayez plus de la moitié des nombres identiques, vous n'obtiendrez jamais des valeurs équivalentes dans un ordre consécutif.

Veuillez pardonner ma réponse de style "moi aussi", mais la réponse de Coady ne pourrait-elle pas être simplifiée?

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)

Edit: Voici une version de python 2 qui renvoie une liste:

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. Compter le nombre de fois où chaque valeur apparaît
2. Sélectionnez les valeurs dans l'ordre du plus fréquent au moins fréquent
3. Ajouter la valeur sélectionnée à la sortie finale, en incrémentant l'index de 2 à chaque fois
4. Réinitialiser l'index à 1 si l'index est hors limites

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