Cuando ordenamos una lista, como

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

elementos iguales son siempre adyacentes en la lista resultante.

¿Cómo puedo lograr la tarea opuesta: barajar la lista para que los elementos iguales nunca sean (o tan raramente 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 listaa, generar una permutaciónp de eso que minimiza el número de paresp[i]==p[i+1].

Como 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 Funciones proporcionadas que generan la mejor permutación posible sin problemas.@tobias_k y David también respondió 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.