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

Ceci est dans la ligne du pseudocode actuellement incomplet de Thijser. L’idée est de prendre le plus fréquent des types d’articles restants, à moins qu’il ne soit juste pris. (Voir également 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 les comptes k1 et k2, la solution optimale a k2 – k1 – 1 défauts si k1 k2. Le cas est évident. Les autres sont symésortingques; chaque instance de l’élément minoritaire empêche au maximum deux défauts sur un total de k1 + k2 – 1 possible.

Cet algorithme glouton renvoie des solutions optimales, par la logique suivante. Nous appelons un préfixe (solution partielle) sûr s’il s’étend à une solution optimale. De toute évidence, le préfixe vide est sûr et si un préfixe sécurisé est une solution complète, cette solution est optimale. Il suffit de montrer par induction que chaque étape gourmande maintient la sécurité.

La seule manière par laquelle une étape gourmande introduit un défaut consiste à ne conserver qu’un seul type d’élément, auquel cas il n’y a qu’un seul moyen de continuer et cette méthode est sûre. Sinon, que P soit le préfixe (sûr) juste avant l’étape considérée, soit P le préfixe juste après, et que S soit une solution optimale en extension de P. Si S étend aussi P ‘, alors nous avons terminé. 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 ne contenant que x et y. Si la première sous-chaîne a au moins autant de x que y, alors 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 y, et nous pouvons réécrire ces sous-chaînes sans défauts supplémentaires pour que x passe en premier. Dans les deux cas, nous trouvons une solution optimale T qui étend P ‘, au besoin.

Supposons maintenant que P se termine par y. Modifiez Q en déplaçant la première occurrence de x vers l’avant. Ce faisant, nous introduisons au maximum 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 et des tests efficaces pour détecter le moment où le choix actuellement envisagé est globalement contraint d’une manière ou d’une autre. Le temps de fonctionnement asymptotique est optimal, car la surcharge de génération est de l’ordre de la longueur de la sortie. Le délai le plus défavorable 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. Boucle sur la première moitié de la liste sortingée et remplit tous les indices pairs de la liste de résultats
3. Boucle sur la seconde moitié de la liste sortingée et remplit tous les indices impairs de la liste de résultats

Vous aurez seulement 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 en des points consécutifs (par le trou du pigeon) principe).

Comme indiqué dans les commentaires, cette approche peut avoir un conflit de trop dans le cas où l’un des éléments se produit au moins n/2 fois (ou n/2+1 pour n impair, ce qui se généralise à (n+1)/2) pour les deux pairs et impairs). Il y a au plus deux de ces éléments et s’il y en a deux, l’algorithme fonctionne correctement. 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 d’abord.

Je ne connais pas assez bien Python pour écrire ceci correctement, alors j’ai pris la liberté de copier l’implémentation d’une version précédente de l’OP à partir 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 commun 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 courants.

 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 sortingées» (qui n’ont pas deux éléments égaux dans les positions adjacentes) en utilisant un algorithme de retour en arrière récursif. En fait, la seule différence avec la génération de 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 dans cette forme, la fonction n’est pas très efficace car elle crée beaucoup de sous-listes. En outre, nous pouvons accélérer le processus en examinant d’abord les nombres les plus limités (ceux avec le plus grand nombre). Voici une version beaucoup plus efficace qui utilise uniquement les counts des nombres.

 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 uniquement la next permutation parfaite, ou une list contenant tous ces éléments. Mais notez que s’il n’y a pas de permutation parfaitement non sortingée, 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 "", line 1, in  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 rechange. Cela garantira le retour d’une permutation parfaitement non sortingée, s’il y en a une, ou une bonne approximation.

 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 sortingé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 sont 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] donc l’ordre dans lequel vous vous retrouvez est tout sauf aléatoire, mais d’après ce que je comprends la question ce n’est pas le hasard que vous recherchez.

L’idée est de diviser la liste sortingée au centre puis d’échanger tous les autres éléments des deux parties.

Pour 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) où tous les autres éléments commençant par 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 combien de fois ils se produisent. Placez la réponse dans une carte.

2. sortingez cette carte pour que les nombres qui surviennent le plus souvent viennent en premier.

3. Le premier numéro de votre réponse est le premier numéro de la carte sortingée.

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

Si vous voulez améliorer l’efficacité, cherchez des moyens d’accroître l’efficacité de l’étape de sorting.

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

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

En réponse à la question sur les 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 sur le plan conceptuel (bien que d’autres puissent être plus rapides dans la pratique car ils se traduisent par un code plus simple). Il n’utilise pas de force brute, il ne génère que des permutations uniques, et les chemins ne conduisant pas aux solutions sont coupés au plus tôt.

J’utiliserai le terme “élément abondant” pour un élément d’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, la série abac ne contient pas d’élément abondant, les ensembles abaca et aabcaa ont a é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 premières 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 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 apparition de l’élément abondant dans la permutation, passez directement à la prochaine permutation.
Par exemple, lorsque la permutation est jusqu’à présent abc , un ensemble contenant un élément abondant a ne peut être inséré que si l’abondance est inférieure ou égale à 2;

5.2. Sélectionnez l’élément de l’ensemble dont la dernière occurrence dans la permutation vient en premier.
p.ex. lorsque la permutation jusqu’à présent abcba et set est ab , sélectionnez b

5.3. Insérez l’élément sélectionné au moins 2 positions à droite de sa dernière occurrence dans la permutation.
par exemple, lorsque vous insérez b dans la permutation babca , les résultats sont babcba et babcab

5.4. Refaire l’étape 5 avec chaque permutation résultante et le rest 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 aa ababac ababca abacb aa abacab abacba abca ab b abcba a - abcab aa abcaba acb aab a acab ab a acaba bb acabab acba ab b acbab aa acbaba bac aab b babc aa a babac aa babaca babca a - bacb aa a bacab aa bacaba bacba a - bca aab - cab aab a caba ab b cabab aa cababa cba aab - 

Cet algorithme génère des permutations uniques. Si vous voulez connaître le nombre total de permutations (où l’ aba est compté deux fois parce que 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 ensemble abcdabcaba ce serait 4! * 3! * 2! * 1! ou 288, ce qui démontre à quel point un algorithme est inefficace et génère toutes les permutations au lieu des seules. Pour lister toutes les permutations dans ce cas, il suffit de lister les permutations uniques 288 fois 🙂

Ci-dessous, une implémentation (plutôt maladroite) en Javascript; Je suspecte qu’un langage comme Python soit 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 + "
"); ++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 + "
"); ++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"]); 

1. Trier 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 place d’origine (par valeur d’élément), il essaiera donc, pour votre exemple, de séparer les 1, 2 et 3 de leurs positions sortingées.

Commencez avec la liste sortingée de longueur n. Soit m = n / 2. Prenez les valeurs à 0, puis m, puis 1, puis m + 1, puis 2, puis m + 2, etc. Sauf si vous avez plus de la moitié des nombres identiques, vous n’obtiendrez jamais de valeurs équivalentes dans un ordre consécutif.

S’il vous plaît pardonnez mon “moi aussi” réponse de style, mais la réponse de Coady ne pourrait-elle pas être simplifiée à cela?

 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. Nombre de fois que chaque valeur apparaît
2. Sélectionner des 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 index hors limites

 from heapq import heapify, heappop def dissortingbute(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) dissortingbuted = [None] * length while counts: count, value = heappop(counts) for _ in xrange(-count): dissortingbuted[index] = value index = index + 2 if index + 2 < length else 1 return distributed