Когда мы сортируем список, как

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

равные элементы всегда находятся рядом в результирующем списке.

Как я могу выполнить противоположную задачу - перетасовать список так, чтобы равные элементы никогда не были (или как можно реже) смежными?

Например, для приведенного выше списка одним из возможных решений является

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

Более формально, учитывая списокaсоздать перестановкуp это минимизирует количество парp[i]==p[i+1].

Поскольку списки велики, генерация и фильтрация всех перестановок невозможна.

Бонусный вопрос: как эффективно генерировать все такие перестановки?

Вот код, который я использую для тестирования решений:https://gist.github.com/gebrkn/9f550094b3d24a35aebd

UPD: Выбор победителя был трудным, потому что многие люди опубликовали отличные ответы.@VincentvanderWeele, @ Дэвид Эйзенстат, @Coady, @ enrico.bacis а также@srgerg предоставил функции, которые генерируют наилучшую возможную перестановку без нареканий.@tobias_k и Дэвид также ответил на бонусный вопрос (генерировать все перестановки). Дополнительные очки Дэвиду для доказательства правильности.

Код из @VincentvanderWeele кажется самым быстрым.