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

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/9f550094b3d24a35aebdUPD：在这里选择获胜者是一个艰难的选择，因为许多人都给出了很好的答案。@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 list

a = sorted(lst)

# Put the element occurring more than half of the times in front (if needed)

n = len(a)

m = (n + 1) // 2

for i in range(n - m + 1):

    if a[i] == a[i + m - 1]:

        a = a[i:] + a[:i]

        break

result = [None] * n

# Loop over the first half of the sorted list and fill all even indices of the result list

for 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 list

for i, elt in enumerate(a[m:]):

    result[2*i+1] = elt

return result

Answer 2

已经给出的算法将剩下的不是前一项的最常见项取走是正确的。这是一个简单的实现，可以最佳地使用堆来跟踪最常见的堆。

import collections, heapq

def 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]