algorithm - todas - permutaciones y combinaciones
Generar todas las permutaciones de una lista sin elementos iguales adyacentes (12)
- Cuente el número de veces que aparece cada valor
- Seleccione valores en orden de más frecuente a menos frecuente
- Agregue el valor seleccionado al resultado final, incrementando el índice en 2 cada vez
- Restablecer índice a 1 si el índice está fuera de límites
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
Cuando ordenamos una lista, como
a = [1,2,3,3,2,2,1]
sorted(a) => [1, 1, 2, 2, 2, 3, 3]
los elementos iguales siempre están adyacentes en la lista resultante.
¿Cómo puedo lograr la tarea opuesta - barajar la lista para que los elementos iguales nunca (o tan rara vez como sea posible) adyacentes?
Por ejemplo, para la lista anterior, una de las posibles soluciones es
p = [1,3,2,3,2,1,2]
Más formalmente, dada una lista a , genere una permutación p que minimice el número de pares p[i]==p[i+1] .
Como las listas son grandes, generar y filtrar todas las permutaciones no es una opción.
Pregunta de bonificación: ¿cómo generar todas esas permutaciones de manera eficiente?
Este es el código que estoy usando para probar las soluciones: https://gist.github.com/gebrkn/9f550094b3d24a35aebd
UPD: Elegir un ganador aquí fue una decisión difícil, porque muchas personas publicaron excelentes respuestas. @VincentvanderWeele , @David Eisenstat , @Coady , @enrico.bacis y @srgerg proporcionaron funciones que generan la mejor permutación posible sin problemas. @tobias_k y David también respondieron la pregunta de bonificación (generar todas las permutaciones). Puntos adicionales para David por la prueba de corrección.
El código de @VincentvanderWeele parece ser el más rápido.
- Ordena la lista
- Genere un "mejor orden aleatorio" de la lista utilizando este algoritmo
Proporcionará el mínimo de elementos de la lista en su lugar original (por valor de artículo), por lo que tratará, para su ejemplo, de poner los 1, 2 y 3 lejos de sus posiciones ordenadas.
Aquí hay un buen algoritmo:
En primer lugar, cuente todos los números con qué frecuencia ocurren. Coloque la respuesta en un mapa.
ordene este mapa para que los números que ocurren con mayor frecuencia estén primero.
El primer número de su respuesta es el primer número en el mapa ordenado.
Recurra al mapa con el primero ahora siendo uno más pequeño.
Si desea mejorar la eficiencia, busque maneras de aumentar la eficiencia del paso de clasificación.
Comience con la lista ordenada de longitud n. Deje m = n / 2. Tome los valores a 0, luego m, luego 1, luego m + 1, luego 2, luego m + 2, y así sucesivamente. A menos que tenga más de la mitad de los números iguales, nunca obtendrá valores equivalentes en orden consecutivo.
El algoritmo ya dado de tomar el elemento más común a la izquierda que no es el elemento anterior es correcto. Aquí hay una implementación simple, que de manera óptima usa un montón para rastrear los más comunes.
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]
En Python puedes hacer lo siguiente.
Considere que tiene una lista ordenada l , puede hacer:
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]
Estas son operaciones in situ y, por lo tanto, deberían ser bastante rápidas ( O(N) ). Tenga en cuenta que pasará de l[i] == l[i+1] a l[i] == l[i+2] por lo que el orden con el que termina es cualquier cosa menos aleatorio, pero a partir de cómo entiendo la pregunta no es la aleatoriedad lo que estás buscando.
La idea es dividir la lista ordenada en el medio y luego intercambiar todos los demás elementos en las dos partes.
Para l= [1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5] esto lleva a l = [3, 1, 4, 2, 5, 1, 3, 1, 4, 2, 5]
El método no puede deshacerse de todo l[i] == l[i + 1] tan pronto como la abundancia de un elemento sea mayor o igual que la mitad de la longitud de la lista.
Mientras que lo anterior funciona bien siempre que la abundancia del elemento más frecuente sea más pequeña que la mitad del tamaño de la lista, la siguiente función también maneja los casos límite (el famoso problema de uno por uno) donde cada otro elemento comienza con el el primero debe ser el más abundante:
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
En respuesta a la pregunta adicional: este es un algoritmo que encuentra todas las permutaciones de un conjunto donde ningún elemento adyacente puede ser idéntico. Creo que este es el algoritmo más eficiente conceptualmente (aunque otros pueden ser más rápidos en la práctica porque se traducen en un código más simple). No usa fuerza bruta, solo genera permutaciones únicas, y las rutas que no conducen a soluciones se cortan en el punto más temprano.
Usaré el término "elemento abundante" para un elemento en un conjunto que ocurre con más frecuencia que todos los demás elementos combinados, y el término "abundancia" para el número de elementos abundantes menos el número de otros elementos.
por ejemplo, el conjunto abac no tiene elemento abundante, los conjuntos aabcaa y aabcaa tienen a como elemento abundante, y abundancia 1 y 2 respectivamente.
- Comience con un conjunto como:
aaabbcd
- Separe las primeras ocurrencias de las repeticiones:
primeros: abcd
repite: aab
- Encuentre el elemento abundante en las repeticiones, si hay alguno, y calcule la abundancia:
elemento abundante: a
abundancia: 1
- Genera todas las permutaciones de las primicias donde el número de elementos después del elemento abundante no es menor que la abundancia: (por lo tanto, en el ejemplo, la "a" no puede ser la última)
abcd, abdc, acbd, acdb, adbc, adcb, bacd, badc, bcad,
bcda, bdac,bdca,
cabd, cadb, cbad,cbda, cdab,cdba, dabc, dacb, abac,dbca, dcab,dcba
- Para cada permutación, inserte el conjunto de caracteres repetidos uno por uno, siguiendo estas reglas:
5.1. Si la abundancia del conjunto es mayor que la cantidad de elementos después de la última ocurrencia del elemento abundante en la permutación hasta el momento, salte a la siguiente permutación.
por ejemplo, cuando la permutación hasta ahora esabc, un conjunto con abundante elementoasolo puede insertarse si la abundancia es 2 o menos, por lo queaaaabcestá bien,aaaaabcno.5.2. Seleccione el elemento del conjunto cuya última ocurrencia en la permutación es lo primero.
por ejemplo, cuando la permutación hasta ahora esabcbay se estableceab, seleccioneb5.3. Inserte el elemento seleccionado al menos 2 posiciones a la derecha de su última aparición en la permutación.
por ejemplo, al insertarben la permutación debabca, los resultados sonbabcbaybabcab5.4. Repita el paso 5 con cada permutación resultante y el resto del conjunto.
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 -
Este algoritmo genera permutaciones únicas. Si desea saber el número total de permutaciones (donde aba se cuenta dos veces porque puede cambiar las a), multiplique el número de permutaciones únicas por un factor:
F = N 1 ! * N 2 ! * ... * N n !
donde N es el número de ocurrencias de cada elemento en el conjunto. ¡Para un conjunto abcdabcaba esto sería 4! * 3! * 2! * 1! o 288, que demuestra cuán ineficiente es un algoritmo que genera todas las permutaciones en lugar de solo las únicas. Para enumerar todas las permutaciones en este caso, simplemente enumere las permutaciones únicas 288 veces :-)
A continuación se muestra una implementación (bastante torpe) en Javascript; Sospecho que un lenguaje como Python puede ser más adecuado para este tipo de cosas. Ejecute el fragmento de código para calcular las permutaciones separadas 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"]);
Esto está en la línea del pseudocódigo actualmente incompleto de Thijser. La idea es tomar el tipo de artículo más frecuente a menos que simplemente se haya tomado. (Véase también la implementación de Coady de este algoritmo).
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
Prueba de corrección
Para dos tipos de elementos, con los recuentos k1 y k2, la solución óptima tiene defectos k2 - k1 - 1 si k1 <k2, 0 defectos si k1 = k2 y k1 - k2 - 1 defectos si k1> k2. El = caso es obvio. Los otros son simétricos; cada instancia del elemento minoritario evita como máximo dos defectos de un total de k1 + k2 - 1 posible.
Este algoritmo codicioso devuelve soluciones óptimas, mediante la siguiente lógica. Llamamos a un prefijo (solución parcial) seguro si se extiende a una solución óptima. Claramente, el prefijo vacío es seguro, y si un prefijo seguro es una solución completa, entonces esa solución es óptima. Basta con mostrar inductivamente que cada paso codicioso mantiene la seguridad.
La única forma en que un paso codicioso introduce un defecto es si solo queda un tipo de elemento, en cuyo caso solo hay una forma de continuar, y de esa manera es seguro. De lo contrario, deje que P sea el prefijo (seguro) justo antes del paso considerado, deje que P ''sea el prefijo justo después y deje que S sea una solución óptima que extiende P. Si S también extiende P'', entonces hemos terminado. De lo contrario, sea P ''= Px y S = PQ y Q = yQ'', donde xey son elementos y Q y Q ''son secuencias.
Supongamos primero que P no termina con y. Por la elección del algoritmo, x es al menos tan frecuente en Q como y. Considere las subcadenas máximas de Q que contienen solo x e y. Si la primera subcadena tiene al menos tantas x como y, entonces puede ser reescrita sin introducir defectos adicionales para comenzar con x. Si la primera subcadena tiene más y''s que x, entonces alguna otra subcadena tiene más x que y, y podemos reescribir estas subcadenas sin defectos adicionales para que x vaya primero. En ambos casos, encontramos una solución T óptima que extiende P '', según sea necesario.
Supongamos ahora que P termina con y. Modifique Q moviendo la primera aparición de x al frente. Al hacerlo, presentamos como máximo un defecto (donde x solía estar) y eliminamos un defecto (el yy).
Generando todas las soluciones
Esta es la respuesta de tobias_k más pruebas eficientes para detectar cuándo la opción actualmente bajo consideración está limitada de alguna manera a nivel mundial. El tiempo de ejecución asintótico es óptimo, ya que la sobrecarga de generación está en el orden de la longitud de la salida. Lamentablemente, el retraso en el peor de los casos es cuadrático; podría reducirse a lineal (óptimo) con mejores estructuras de datos.
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))])
La idea es ordenar los elementos de los más comunes a los menos comunes, tomar los más comunes, disminuir su conteo y volver a colocarlos en la lista manteniendo el orden descendente (pero evitando poner el último elemento usado primero para evitar repeticiones cuando sea posible) .
Esto se puede implementar usando Counter y 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
Ejemplo
>>> 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]
Perdone mi respuesta de estilo "yo también", pero ¿no podría simplificarse la respuesta de Coady ?
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)
Editar: Aquí hay una versión de python 2 que devuelve una lista:
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
Pseudocódigo:
- Ordene la lista
- Pasa el cursor por la primera mitad de la lista ordenada y completa todos los índices pares de la lista de resultados
- Pasa por la segunda mitad de la lista ordenada y completa todos los índices impares de la lista de resultados
Solo tendrá p[i]==p[i+1] si más de la mitad de la entrada consiste en el mismo elemento, en cuyo caso no hay otra opción que colocar el mismo elemento en puntos consecutivos (por el agujero del pidgeon principio).
Como se señala en los comentarios, este enfoque puede tener un conflicto demasiado en caso de que uno de los elementos ocurra al menos n/2 veces (o n/2+1 para n impar, esto se generaliza a (n+1)/2) para ambos, par e impar). Hay como mucho dos de esos elementos y si hay dos, el algoritmo funciona bien. El único caso problemático es cuando hay un elemento que ocurre al menos la mitad del tiempo. Simplemente podemos resolver este problema encontrando el elemento y tratando con él primero.
No sé lo suficiente sobre python para escribir esto correctamente, así que me tomé la libertad de copiar la implementación del OP de una versión anterior 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
Puede generar todas las permutaciones ''perfectamente sin clasificar'' (que no tienen dos elementos iguales en posiciones adyacentes) utilizando un algoritmo de retroceso recursivo. De hecho, la única diferencia para generar todas las permutaciones es que realiza un seguimiento del último número y excluye algunas soluciones en consecuencia:
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 []
Tenga en cuenta que en esta forma la función no es muy eficiente, ya que crea muchas sublistas. Además, podemos acelerarlo mirando primero los números más restringidos (aquellos con el recuento más alto). Aquí hay una versión mucho más eficiente que usa solo los counts de los números.
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))
Puede usar esto para generar la next permutación perfecta, o una list contenga a todos. Pero tenga en cuenta que si no hay una permutación perfectamente desordenada, este generador no dará ningún resultado.
>>> 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
Para evitar este problema, puede usar esto junto con uno de los algoritmos propuestos en las otras respuestas como una alternativa. Esto garantizará devolver una permutación perfectamente desordenada, si hay una, o una buena aproximación de lo contrario.
def unsort_safe(lst):
try:
return next(unsort_generator(lst))
except StopIteration:
return unsort_fallback(lst)