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

Quando ordenamos 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 para que elementos iguais nunca sejam (ou o mais raramente possível) 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 listaa, gerar uma permutaçãop dele que minimiza o número de paresp[i]==p[i+1].

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

Pergunta de bônus: como gerar todas essas permutações com eficiência?

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 forneceu funções que geram a melhor permutação possível na perfeição.@tobias_k e David também respondeu à pergunta do bônus (gere todas as permutações). Pontos adicionais para David pela prova de correção.

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