当我们对列表进行排序时,比如
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,@大卫Eisenstat,@Coady,@ enrico.bacis和@srgerg提供函数完美产生的最佳可能的排列.@tobias_k和大卫也回答了红利问题(生成所有排列).大卫的其他要点是正确性证明.
来自@VincentvanderWeele的代码似乎是最快的.