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

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

这与Thijser当前不完整的伪代码是一致的。这个想法是采取剩余物品类型中最频繁的一种，除非是刚采取的。（另请参见Coady对该算法的实现。）

import collectionsimport heapqclass Sentinel:    passdef david_eisenstat(lst):    counts = collections.Counter(lst)    heap = [(-count, key) for key, count in counts.items()]    heapq.heapify(heap)    output = []    last = Sentinel()    while heap:        minuscount1, key1 = heapq.heappop(heap)        if key1 != last or not heap: last = key1 minuscount1 += 1        else: minuscount2, key2 = heapq.heappop(heap) last = key2 minuscount2 += 1 if minuscount2 != 0:     heapq.heappush(heap, (minuscount2, key2))        output.append(last)        if minuscount1 != 0: heapq.heappush(heap, (minuscount1, key1))    return output

正确性证明

对于计数为k1和k2的两种物料类型，最优解在k1 k2时具有k1-
k2-1缺陷。=的情况很明显。其他是对称的。少数元素的每个实例最多可以防止总共k1 + k2-1中的两个缺陷。

该贪婪算法通过以下逻辑返回最优解。如果前缀（部分解决方案）扩展到最佳解决方案，则称其为 安全的
。显然，空前缀是安全的，并且如果安全前缀是完整的解决方案，则该解决方案是最佳的。足以归纳地表明每个贪婪的步骤都可以确保安全。

贪婪步骤引入缺陷的唯一方法是仅保留一种物料类型，在这种情况下，只有一种方法可以继续，并且这种方法是安全的。否则，让P为所考虑步骤之前的（安全）前缀，让P’为紧随其后的前缀，让S为扩展P的最优解。如果S也扩展P’，那么我们就完成了。否则，令P’=
Px且S = PQ且Q = yQ’，其中x和y为项目，Q和Q’为序列。

首先假设P不以y结尾。根据算法的选择，x在Q中的频率至少与y相同。考虑仅包含x和y的Q的最大子串。如果第一个子字符串至少具有与y一样多的x，则可以重写它而不会引入以x开头的其他缺陷。如果第一个子字符串的y比x的多，那么其他一些子字符串的x则比y的多，我们可以重写这些子字符串而没有其他缺陷，因此x优先。在两种情况下，我们都根据需要找到扩展P’的最优解T。

现在假设P以y结尾。通过将x的第一个出现位置移到最前面来修改Q。这样做时，我们最多引入一个缺陷（x曾经是）并消除一个缺陷（yy）。

生成所有解决方案

这是tobias_k的答案，加上有效的测试，以检测当前正在考虑的选择何时在某种程度上受到全局限制。渐近运行时间是最佳的，因为生成的开销大约是输出长度的数量。不幸的是，最坏情况下的延迟是二次的。可以使用更好的数据结构将其减少为线性（最佳）。

from collections import Counterfrom itertools import permutationsfrom operator import itemgetterfrom random import randrangedef get_mode(count):    return max(count.items(), key=itemgetter(1))[0]def enum2(prefix, x, count, total, mode):    prefix.append(x)    count_x = count[x]    if count_x == 1:        del count[x]    else:        count[x] = count_x - 1    yield from enum1(prefix, count, total - 1, mode)    count[x] = count_x    del prefix[-1]def enum1(prefix, count, total, mode):    if total == 0:        yield tuple(prefix)        return    if count[mode] * 2 - 1 >= total and [mode] != prefix[-1:]:        yield from enum2(prefix, mode, count, total, mode)    else:        defect_okay = not prefix or count[prefix[-1]] * 2 > total        mode = get_mode(count)        for x in list(count.keys()): if defect_okay or [x] != prefix[-1:]:     yield from enum2(prefix, x, count, total, mode)def enum(seq):    count = Counter(seq)    if count:        yield from enum1([], count, sum(count.values()), get_mode(count))    else:        yield ()def defects(lst):    return sum(lst[i - 1] == lst[i] for i in range(1, len(lst)))def test(lst):    perms = set(permutations(lst))    opt = min(map(defects, perms))    slow = {perm for perm in perms if defects(perm) == opt}    fast = set(enum(lst))    print(lst, fast, slow)    assert slow == fastfor r in range(10000):    test([randrange(3) for i in range(randrange(6))])