Gera todas as permutações de uma lista sem elementos iguais adjacentes

Quando classificamos uma lista, como

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

elementos iguais são sempre adjacentes na lista resultante.

Como posso realizar a tarefa oposta - embaralhar a lista de forma que elementos iguais nunca (ou tão raramente quanto possível) sejam adjacentes?

Por exemplo, para a lista acima, uma das soluções possíveis é

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

Mais formalmente, dada uma lista a, gere uma permutação pdela que minimize o número de pares p[i]==p[i+1].

Como as listas são grandes, gerar e filtrar todas as permutações não é uma opção.

Pergunta bônus: como gerar todas essas permutações de forma eficiente?

Este é o código que estou usando para testar as soluções: https://gist.github.com/gebrkn/9f550094b3d24a35aebd

UPD: escolher um vencedor aqui foi uma escolha difícil, porque muitas pessoas postaram respostas excelentes. @VincentvanderWeele , @David Eisenstat , @Coady , @ enrico.bacis e @srgerg fornecem funções que geram a melhor permutação possível sem falhas. @tobias_k e David também responderam à pergunta bônus (gerar todas as permutações). Pontos adicionais para David pela prova de correção.

O código de @VincentvanderWeele parece ser o mais rápido.

Isso segue as linhas do pseudocódigo atualmente incompleto de Thijser. A ideia é pegar o mais frequente dos tipos de itens restantes, a menos que tenha acabado de ser levado. (Veja também a implementação deste algoritmo de 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

Prova de correção

Para dois tipos de itens, com contagens k1 e k2, a solução ótima tem k2 - k1 - 1 defeitos se k1 <k2, 0 defeitos se k1 = k2 e k1 - k2 - 1 defeitos se k1> k2. O caso = é óbvio. Os outros são simétricos; cada instância do elemento minoritário evita no máximo dois defeitos de um total de k1 + k2 - 1 possível.

Este algoritmo guloso retorna soluções ótimas, pela seguinte lógica. Chamamos um prefixo (solução parcial) de seguro se ele se estende a uma solução ótima. Claramente, o prefixo vazio é seguro, e se um prefixo seguro for uma solução completa, então essa solução é ótima. Basta mostrar indutivamente que cada passo ganancioso mantém a segurança.

A única maneira de uma etapa gananciosa introduzir um defeito é se apenas um tipo de item permanecer; nesse caso, há apenas uma maneira de continuar e essa maneira é segura. Caso contrário, seja P o prefixo (seguro) logo antes da etapa em consideração, seja P 'o prefixo logo depois e seja S uma solução ótima estendendo P. Se S estende P' também, então está feito. Caso contrário, seja P '= Px e S = PQ e Q = yQ', onde x e y são itens e Q e Q 'são sequências.

Suponha primeiro que P não termine com y. Pela escolha do algoritmo, x é pelo menos tão frequente em Q quanto y. Considere as substrings máximas de Q contendo apenas x e y. Se a primeira substring tiver pelo menos tantos x quanto y, ela poderá ser reescrita sem introduzir defeitos adicionais para começar com x. Se a primeira substring tiver mais y's do que x's, então alguma outra substring terá mais x's do que y's, e podemos reescrever essas substrings sem defeitos adicionais para que x vá primeiro. Em ambos os casos, encontramos uma solução ótima T que estende P ', conforme necessário.

Suponha agora que P termine com y. Modifique Q movendo a primeira ocorrência de x para a frente. Ao fazer isso, introduzimos no máximo um defeito (onde costumava ser x) e eliminamos um defeito (o yy).

Gerando todas as soluções

Esta é a resposta de tobias_k mais testes eficientes para detectar quando a escolha atualmente em consideração é globalmente restrita de alguma forma. O tempo de execução assintótico é ótimo, uma vez que a sobrecarga de geração é da ordem do comprimento da saída. O atraso do pior caso, infelizmente, é quadrático; poderia ser reduzido a linear (ótimo) com melhores estruturas de dados.

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

Pseudo-código:

1. Classifique a lista
2. Percorre a primeira metade da lista ordenada e preenche todos os índices pares da lista de resultados
3. Percorre a segunda metade da lista ordenada e preenche todos os índices ímpares da lista de resultados

Você só terá p[i]==p[i+1]se mais da metade da entrada consistir no mesmo elemento, caso em que não há outra escolha a não ser colocar o mesmo elemento em pontos consecutivos (pelo princípio do pidgeon hole).

Conforme apontado nos comentários, esta abordagem pode ter um conflito a mais no caso de um dos elementos ocorrer pelo menos n/2vezes (ou n/2+1para ímpar n; isso generaliza para (n+1)/2)para par e ímpar). Existem no máximo dois desses elementos e, se houver dois, o algoritmo funciona bem. O único caso problemático é quando há um elemento que ocorre pelo menos metade do tempo. Podemos simplesmente resolver esse problema encontrando o elemento e lidando com ele primeiro.

Não sei o suficiente sobre python para escrever isso corretamente, então tomei a liberdade de copiar a implementação do OP de uma versão anterior do 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

O algoritmo já fornecido de pegar o item mais comum restante que não é o item anterior está correto. Aqui está uma implementação simples, que usa um heap para rastrear o mais comum.

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]

Você pode gerar todas as permutações 'perfeitamente não classificadas' (que não têm dois elementos iguais em posições adjacentes) usando um algoritmo de retrocesso recursivo. Na verdade, a única diferença para gerar todas as permutações é que você mantém o controle do último número e exclui algumas soluções de acordo:

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

Observe que neste formulário a função não é muito eficiente, pois cria muitas sublistas. Além disso, podemos acelerar olhando primeiro para os números mais restritos (aqueles com a contagem mais alta). Esta é uma versão muito mais eficiente usando apenas o countsdos 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))

Você pode usar isso para gerar apenas a nextpermutação perfeita ou listreter todos eles. Mas observe que, se não houver uma permutação perfeitamente não classificada, esse gerador, conseqüentemente, não produzirá resultados.

>>> 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 contornar esse problema, você pode usar isso junto com um dos algoritmos propostos nas outras respostas como um fallback. Isso garantirá o retorno de uma permutação perfeitamente não classificada, se houver, ou uma boa aproximação caso contrário.

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

Em python, você pode fazer o seguinte.

Considere que você tem uma lista classificada l, você pode fazer:

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 são apenas operações locais e, portanto, devem ser bastante rápidas ( O(N)). Observe que você mudará de l[i] == l[i+1]para, de l[i] == l[i+2]modo que a ordem com que você terminar é tudo menos aleatório, mas pelo que entendi a pergunta, não é aleatoriedade que você está procurando.

A ideia é dividir a lista classificada no meio e, em seguida, trocar todos os outros elementos nas duas partes.

Pois l= [1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5]isso leva al = [3, 1, 4, 2, 5, 1, 3, 1, 4, 2, 5]

O método falha em eliminar todos os l[i] == l[i + 1]logo que a abundância de um elemento seja maior ou igual a metade do comprimento da lista.

Embora o procedimento acima funcione bem, desde que a abundância do elemento mais frequente seja menor que a metade do tamanho da lista, a função a seguir também lida com os casos limites (o famoso problema off-by-one) em que todos os outros elementos começando com o primeiro deve ser o mais 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

Aqui está um bom algoritmo:

1. Em primeiro lugar, conte para todos os números a frequência com que ocorrem. Coloque a resposta em um mapa.

2. classifique esse mapa de forma que os números que ocorrem com mais frequência venham primeiro.

3. O primeiro número de sua resposta é o primeiro número no mapa classificado.

4. Recorra ao mapa com o primeiro sendo agora um menor.

Se você deseja melhorar a eficiência, procure maneiras de aumentar a eficiência da etapa de classificação.

Em resposta à pergunta bônus: este é um algoritmo que encontra todas as permutações de um conjunto onde nenhum elemento adjacente pode ser idêntico. Acredito que este seja o algoritmo mais eficiente conceitualmente (embora outros possam ser mais rápidos na prática porque se traduzem em um código mais simples). Ele não usa força bruta, apenas gera permutações únicas, e os caminhos que não levam a soluções são interrompidos no ponto inicial.

Usarei o termo "elemento abundante" para um elemento em um conjunto que ocorre com mais freqüência do que todos os outros elementos combinados, e o termo "abundância" para o número de elementos abundantes menos o número de outros elementos.
por exemplo, o conjunto abacnão tem elemento abundante, os conjuntos abacae aabcaatêm acomo elemento abundante e abundância 1 e 2, respectivamente.

1. Comece com um conjunto como:

aaabbcd

2. Separe as primeiras ocorrências das repetições:

primeiros: abcd
repete: aab

3. Encontre o elemento abundante nas repetições, se houver, e calcule a abundância:

elemento abundante: uma
abundância: 1

4. Gere todas as permutações dos primeiros onde o número de elementos após o elemento abundante não é menor que a abundância: (portanto, no exemplo, o "a" não pode ser o ú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 permutação, insira o conjunto de caracteres repetidos um a um, seguindo estas regras:

5.1. Se a abundância do conjunto for maior do que o número de elementos após a última ocorrência do elemento abundante na permutação até agora, pule para a próxima permutação.
por exemplo, quando a permutação até agora é abc, um conjunto com elemento abundante asó pode ser inserido se a abundância for 2 ou menos, então aaaabcestá ok, aaaaabcnão é.

5,2 Selecione o elemento do conjunto cuja última ocorrência na permutação vem primeiro.
por exemplo, quando a permutação até agora é abcbae o conjunto é ab, selecioneb

5,3. Insira o elemento selecionado pelo menos 2 posições à direita de sua última ocorrência na permutação.
por exemplo, ao inserir bna permutação babca, os resultados são babcbaebabcab

5,4 Percorra novamente a etapa 5 com cada permutação resultante e o resto do 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 gera permutações únicas. Se você quiser saber o número total de permutações (onde abaé contado duas vezes porque você pode trocar os a's), multiplique o número de permutações únicas por um fator:

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

onde N é o número de ocorrências de cada elemento do conjunto. Para um conjunto, abcdabcabaisso seria 4! * 3! * 2! * 1! ou 288, que demonstra quão ineficiente é um algoritmo que gera todas as permutações em vez de apenas as únicas. Para listar todas as permutações neste caso, apenas liste as permutações exclusivas 288 vezes :-)

Abaixo está uma implementação (um tanto desajeitada) em Javascript; Suspeito que uma linguagem como o Python pode ser mais adequada para esse tipo de coisa. Execute o trecho de código para calcular as permutações 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"]);

A ideia é ordenar os elementos do mais comum ao menos comum, pegar o mais comum, diminuir sua contagem e colocá-lo de volta na lista mantendo a ordem decrescente (mas evitando colocar o último elemento usado primeiro para evitar repetições quando possível) .

Isso pode ser implementado usando Countere 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

Exemplo

>>> 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. Classifique a lista.
2. Gere um "melhor embaralhamento" da lista usando este algoritmo

Ele fornecerá o mínimo de itens da lista em seus lugares originais (por valor de item), então tentará, por exemplo, colocar os 1s, 2s e 3s longe de suas posições classificadas.

Comece com a lista classificada de comprimento n. Seja m = n / 2. Pegue os valores de 0, depois m, depois 1, depois m + 1, depois 2, depois m + 2 e assim por diante. A menos que você tenha mais da metade dos números iguais, você nunca obterá valores equivalentes em ordem consecutiva.

Por favor, perdoe minha resposta no estilo "eu também", mas a resposta de Coady não poderia ser simplificada para isso?

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: aqui está uma versão do python 2 que retorna uma 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. Conte o número de vezes que cada valor aparece
2. Selecione os valores em ordem do mais frequente ao menos frequente
3. Adicione o valor selecionado à saída final, incrementando o índice em 2 cada vez
4. Redefina o índice para 1 se o índice estiver fora dos limites

from heapq import heapify, heappop
def distribute(values):
    counts = defaultdict(int)
    for value in values:
        counts[value] += 1
    counts = [(-count, key) for key, count in counts.iteritems()]
    heapify(counts)
    index = 0
    length = len(values)
    distributed = [None] * length
    while counts:
        count, value = heappop(counts)
        for _ in xrange(-count):
            distributed[index] = value
            index = index + 2 if index + 2 < length else 1
    return distributed