Genere todas las permutaciones de una lista sin elementos iguales adyacentes

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.

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

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

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]

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)

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

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.

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

2. Separe las primeras ocurrencias de las repeticiones:

firsts: abcd
repite: aab

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

elemento abundante: una
abundancia: 1

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

5. 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 ₁ ! * N ₂ ! * ... * 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"]);

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]

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.

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.

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

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