Genere todas las permutaciones de una lista sin elementos iguales adyacentes

87

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 son siempre adyacentes en la lista resultante.

¿Cómo puedo lograr la tarea opuesta: mezclar la lista de modo que los elementos iguales nunca (o tan rara vez como sea posible) sean 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 pde la misma que minimice el número de pares p[i]==p[i+1].

Dado que las listas son grandes, generar y filtrar todas las permutaciones no es una opción.

Pregunta adicional: ¿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 adicional (generar todas las permutaciones). Puntos adicionales a David por la prueba de corrección.

El código de @VincentvanderWeele parece ser el más rápido.

georg
fuente
1
¿Entonces solo te preocupas por la igualdad ? algo como [1, 2, 1, 3, 1, 4, 1, 5]es exactamente lo mismo que [1, 3, 1, 2, 1, 4, 1, 5]según su criterio?
Bakuriu
1
No puede haber un algoritmo "eficiente". Tome una lista como [1, 1, 1, ..., 2, 3, 4, ..., N]con 2Nelementos. Puedes poner un número n > 1entre cada par de consecutivos 1para obtener una buena permutación. Luego permuta los N/2elementos y obtiene todas las permutaciones válidas (lo que significa que ninguna es mala, pero puede haber más). El número de tales permutaciones es O (N ^ 2), por lo que no puede hacerlo mejor que O (N ^ 2). Sin embargo, todavía mejor que O (N ^ 3) del enfoque ingenuo.
Bakuriu
6
@Bakuriu: Dos cosas: (1) para ser claros, su ejemplo muestra que no puede haber un algoritmo eficiente para la pregunta adicional . (2) Enumerar todas las soluciones óptimas para su ejemplo es O ((N / 2)!), Que es mucho peor que O (N ^ 2) (es decir, su ejemplo es mucho más fuerte de lo que se dio cuenta :-)
j_random_hacker
11
@msw: Estoy creando un sitio web y hay una fila con bloques de anuncios de diferentes proveedores. Quiero organizarlos de modo que no haya bloques del mismo proveedor uno al lado del otro.
georg
2
No diría que esto "ni siquiera se acerca a un duplicado", pero el supuesto duplicado es una pregunta diferente, ya que se considera la distancia entre elementos idénticos. Personas que votaron para cerrar después del comentario de WhyCry: presten más atención en el futuro.
David Eisenstat

Respuestas:

30

Esto está en la línea del pseudocódigo actualmente incompleto de Thijser. La idea es tomar el más frecuente de los tipos de elementos restantes, a menos que se acabe de tomar. (Consulte 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 recuentos k1 y k2, la solución óptima tiene k2 - k1 - 1 defectos 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 previene 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 seguro a un prefijo (solución parcial) 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 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 esa forma es segura. De lo contrario, sea P el prefijo (seguro) justo antes del paso en consideración, sea P 'el prefijo inmediatamente después y sea S una solución óptima que extiende P. Si S extiende P' también, 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 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 se puede reescribir sin introducir defectos adicionales para comenzar con x. Si la primera subcadena tiene más y 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 óptima T que extiende P ', según sea necesario.

Supongamos ahora que P termina en y. Modifique Q moviendo la primera aparición de x al frente. Al hacerlo, introducimos como máximo un defecto (donde solía estar x) 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 que se está considerando actualmente está restringida globalmente de alguna manera. El tiempo de ejecución asintótico es óptimo, ya que la sobrecarga de generación es del orden de la longitud de la salida. Lamentablemente, el retraso del 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))])
David Eisenstat
fuente
23

Pseudocódigo:

  1. Ordenar la lista
  2. Recorra la primera mitad de la lista ordenada y complete todos los índices pares de la lista de resultados
  3. Recorra la segunda mitad de la lista ordenada y complete 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 poner el mismo elemento en puntos consecutivos (por el principio de pidgeon hole).


Como se señaló en los comentarios, este enfoque puede tener un conflicto de más en caso de que uno de los elementos ocurra al menos n/2veces (o n/2+1para impares n; esto se generaliza (n+1)/2)para pares e impares). Hay como máximo dos de estos 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 ocupándonos de é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
Vincent van der Weele
fuente
Según tengo entendido, esto es lo que hace @jojo , no siempre lo óptimo.
georg
10
Esto falla para [0, 1, 1]o [0, 0, 1], dependiendo de si usa índices basados ​​en 0 o basados ​​en 1.
flornquake
@georg De hecho, este es el mismo enfoque que en mi respuesta. (¡Tenga en cuenta que Heuster respondió antes que yo!). En mi código, sin embargo, los pasos 2. y 3. están combinados, optimizando así la eficiencia.
jojo
3
@flornquake ¡Buena captura! Me temo que es el viejo error de uno por uno. Por lo tanto, este enfoque no es óptimo, ya que puede tener 1 conflicto de más.
Vincent van der Weele
1
@Heuster: ¡todas las luces están en verde! "0 fallos".
georg
10

El algoritmo ya dado de tomar el elemento más común que queda que no es el elemento anterior es correcto. Aquí hay una implementación simple, que utiliza de manera óptima 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]
A. Coady
fuente
Buen ejemplo de cómo NO escribir algoritmos en Python. Es simple pero requiere 30 minutos solo para digerir la sintaxis.
alex904
8

Puede generar todas las permutaciones 'perfectamente desordenadas' (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 de 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 countslos 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 solo la nextpermutación perfecta, o listmantenerlas todas. Pero tenga en cuenta que si no hay una permutación perfectamente desordenada, entonces 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 usarlo junto con uno de los algoritmos propuestos en las otras respuestas como alternativa. Esto garantizará devolver una permutación perfectamente sin clasificar, si la hay, o una buena aproximación en caso contrario.

def unsort_safe(lst):
    try:
        return next(unsort_generator(lst))
    except StopIteration:
        return unsort_fallback(lst)
tobias_k
fuente
Esto usa memoria O (N ^ 2) ... para cada elemento en la permutación está haciendo una copia de la lista para la llamada recursiva. Además, al ser recursivo, falla con longitudes "pequeñas".
Bakuriu
@Bakuriu De acuerdo, eso es lo que quise decir con "no optimizado para la eficiencia" ... aunque debo admitir que no lo hice excepto el espacio O (n ^ 2), pero tienes razón ... intentaré mejorarlo .
tobias_k
O (N ^ 2) siempre está detrás de la espalda cuando tienes una resurrección como T(n+1) = something + T(n).
Bakuriu
@tobias_k: ¿podrías publicar una función para una sola permanente, para probar?
georg
@georg Seguro: next(unsort2(collections.Counter(a)));-) Pero dado que este algoritmo genera todas las posibilidades, ¿por qué no comprobarlas todas? Son solo 38 para esa lista de prueba de 7 elementos.
tobias_k
5

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 simplemente en el lugar y, por lo tanto, deberían ser bastante rápidas ( O(N)). Tenga en cuenta que cambiará de l[i] == l[i+1]a l[i] == l[i+2]para que el orden con el que termine sea cualquier cosa menos aleatorio, pero por lo que entiendo la pregunta, lo que está buscando no es la aleatoriedad.

La idea es dividir la lista ordenada en el medio y luego intercambiar todos los demás elementos en las dos partes.

Porque l= [1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5]esto lleva al = [3, 1, 4, 2, 5, 1, 3, 1, 4, 2, 5]

El método no logra deshacerse de todos l[i] == l[i + 1]tan pronto como la abundancia de un elemento es mayor o igual a la mitad de la longitud de la lista.

Si bien lo anterior funciona bien siempre que la abundancia del elemento más frecuente sea menor 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 todos los demás elementos comienzan 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
jojo
fuente
¡Gracias! Esto falla para [3, 2, 1, 2, 1, 3, 2](devuelve [2, 1, 3, 1, 2, 2, 3], debería ser (3, 2, 1, 2, 1, 3, 2)) - vea la esencia
georg
@georg lo siento, mi mal me olvidé de un +1. Inténtelo de nuevo ahora.
jojo
Aún hay problemas, [1, 3, 3, 3, 3, 1, 1]=>[3, 1, 3, 3, 1, 3, 1]
georg
@georg, como señalé, funciona siempre que el más abundante esté presente menos de la mitad de la longitud de la lista, lo que no es el caso en este ejemplo.
jojo
@georg Así que agregué la parte que maneja el error de uno por uno. Esta parte no es particularmente rápida (casi lo mismo que el algoritmo sugerido por Thijser), aunque solo se ejecutará en casos excepcionales.
jojo
5

Aquí hay un buen algoritmo:

  1. En primer lugar, cuente para todos los números la frecuencia con la que ocurren. Coloque la respuesta en un mapa.

  2. Ordene este mapa para que los números que aparecen con mayor frecuencia sean los primeros.

  3. El primer número de su respuesta es el primer número en el mapa ordenado.

  4. Recurre al mapa con el primero ahora más pequeño.

Si desea mejorar la eficiencia, busque formas de aumentar la eficiencia del paso de clasificación.

Thijser
fuente
Sí, esto es lo que hizo @tobias_k. ¡Parece funcionar bien!
georg
@georg Es un poco diferente ... Utilizo el contador solo para reducir la complejidad del espacio, pero no pruebo los números en ningún orden específico (pensé que esto podría ser otra aceleración). Lo que es diferente es que mi solución siempre produce todas las permutaciones 'perfectas', si las hay , mientras que esto debería producir la mejor (?) Solución (perfecta o no).
tobias_k
3
Este pseudocódigo no es del todo correcto; si los recuentos de elementos son 5 x, 2 y, 2 z, entonces juntará x innecesariamente. Vea mi respuesta para una solución.
David Eisenstat
1
Convenido. Por ejemplo, [1,1,1,2,3] esto producirá, por ejemplo, [1,1,2,1,3] en lugar de [1,2,1,3,1].
tobias_k
El paso 3 es realmente contraproducente. Si un número es común (al menos dos entradas más que el siguiente número más frecuente), el paso 3 usará ese número dos veces seguidas, sin ninguna justificación.
MSalters
5

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 la fuerza bruta, solo genera permutaciones únicas y los caminos 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 abacno tiene elemento abundante, los conjuntos abacay aabcaatienen acomo elemento abundante y abundancia 1 y 2 respectivamente.

  1. Comience con un conjunto como:

aaabbcd

  1. Separe las primeras ocurrencias de las repeticiones:

firsts: abcd
repite: aab

  1. Encuentre el elemento abundante en las repeticiones, si las hay, y calcule la abundancia:

elemento abundante: una
abundancia: 1

  1. Genere todas las permutaciones de los primeros donde el número de elementos después del elemento abundante no sea menor que la abundancia: (por lo que en el ejemplo, la "a" no puede ser el último)

abcd, abdc, acbd, acdb, adbc, adcb, bacd, badc, bcad, bcda , bdac, bdca ,
cabd, cadb, cbad, cbda , cdab, cdba , dabc, dacb, abac, dbca , dcab, dcba

  1. 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 el número de elementos después de la última aparición del elemento abundante en la permutación hasta el momento, pase a la siguiente permutación.
por ejemplo, cuando la permutación hasta ahora es abc, un conjunto con elemento abundante asolo se puede insertar si la abundancia es 2 o menos, por lo que aaaabcestá bien, aaaaabcno lo es.

5.2. Seleccione el elemento del conjunto cuya última aparición en la permutación es lo primero.
por ejemplo, cuando la permutación hasta ahora es abcbay el conjunto es ab, seleccioneb

5.3. Inserte el elemento seleccionado al menos 2 posiciones a la derecha de su última aparición en la permutación.
Por ejemplo, al insertar ben permutación babca, los resultados son babcbaybabcab

5.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 abase 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 abcdabcabaesto 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"]);

m69 '' sarcástico y poco acogedor ''
fuente
1
¡gracias por esto! verá si esto se puede acortar un poco en javascript.
stt106
4

La idea es ordenar los elementos del más común al menos común, tomar el más común, disminuir su recuento y volver a colocarlo en la lista manteniendo el orden descendente (pero evitando poner primero el último elemento usado para evitar repeticiones cuando sea posible) .

Esto se puede implementar usando Countery 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]
enrico.bacis
fuente
Esto falla, por ejemplo: [1, 1, 2, 3]donde hay soluciones como [1, 2, 1, 3].
Bakuriu
Sí, me acabo de dar cuenta de eso, lo siento
enrico.bacis
¡Gracias! Esto no siempre produce el resultado óptimo, por ejemplo [1, 2, 3, 2, 3, 2, 2], devuelve [2, 3, 1, 2, 3, 2, 2](1 falla), mientras que el ideal es (2, 1, 2, 3, 2, 3, 2)) - vea la esencia.
georg
@georg Es cierto, buen truco, lo he actualizado manteniendo el principio simple que usa.
enrico.bacis
@ enrico.bacis: ¡gracias! La nueva versión funciona a la perfección. He actualizado la esencia. Lástima que ya no pueda votarte a favor.
georg
2
  1. Ordena la lista.
  2. Genere una "mejor reproducción aleatoria" de la lista utilizando este algoritmo

Dará el mínimo de elementos de la lista en su lugar original (por valor de elemento) por lo que intentará, por ejemplo, poner los 1, 2 y 3 lejos de sus posiciones ordenadas.

Paddy3118
fuente
Lo intenté best_shuffley generó [1,1,1,2,3] -> [3, 1, 2, 1, 1], ¡no es ideal!
georg
2

Comience con la lista ordenada de longitud n. Sea m = n / 2. Tome los valores en 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.

rchuso
fuente
Gracias por la idea. Creo que esto es lo que implementó @Heuster.
georg
2

Por favor, perdone mi respuesta de estilo "yo también", pero ¿no podría simplificarse la respuesta de Coady a esto?

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
srgerg
fuente
Sí, esto parece funcionar bien (excepto que estoy en py2 y la función debería devolver una lista).
georg
@georg Ok, agregué una versión de Python 2 que devuelve una lista.
srgerg
2
  1. Cuente el número de veces que aparece cada valor
  2. Seleccione los valores en orden de más frecuente a menos frecuente
  3. Agregue el valor seleccionado a la salida final, incrementando el índice en 2 cada vez
  4. Restablecer el í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
Joel
fuente