生成列表的所有排列，而没有相邻的相等元素

Question

当我们对列表进行排序时，例如

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和David也回答了奖金问题（生成所有排列）。大卫还提供了正确性证明。

@VincentvanderWeele的代码似乎是最快的。

Answer 1

伪代码：排序清单循环遍历排序列表的前半部分，并填充结果列表的所有偶数索引循环遍历排序列表的后半部分，并填充结果列表的所有奇数索引仅p[i]==p[i+1]当输入的一半以上包含相同元素时，您才可以使用，在这种情况下，除了将相同元素放置在连续的点上之外，别无选择（根据皮氏孔原理）。如评论中所指出的那样，如果其中一个元素至少发生n/2几次（或n/2+1为奇数n；这种情况一般(n+1)/2)适用于偶数和奇数），则这种方法可能会有太多冲突。最多有两个这样的元素，如果有两个，该算法就可以正常工作。唯一有问题的情况是，至少有一半时间出现一个元素。我们可以通过找到元素并首先对其进行处理来简单地解决此问题。我对python不够了解，无法正确编写此代码，因此我自由地从github复制了OP先前版本的实现：# Sort the lista = sorted(lst)# Put the element occurring more than half of the times in front (if needed)n = len(a)m = (n + 1) // 2for i in range(n - m + 1):    if a[i] == a[i + m - 1]:        a = a[i:] + a[:i]        breakresult = [None] * n# Loop over the first half of the sorted list and fill all even indices of the result listfor 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 listfor i, elt in enumerate(a[m:]):    result[2*i+1] = eltreturn result

Answer 2

已经给出的算法将剩下的不是前一项的最常见项取走是正确的。这是一个简单的实现，可以最佳地使用堆来跟踪最常见的堆。import collections, heapqdef 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]