python - 生成没有相邻相等元素的列表的所有排列

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 , @David Eisenstat , @Coady , @enrico.bacis和 @srgerg提供了完美地生成最佳排列的函数。 @tobias_k大卫还回答了奖金问题(生成所有排列)。向 David 提出正确性证明的额外要点。

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

Answer 1

这与 Thijser 目前不完整的伪代码类似。这个想法是采用最常见的剩余项目类型，除非它刚刚被采用。 (另见该算法的 Coady's implementation。)

import collections
import heapq


class Sentinel:
    pass


def 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，则最优解决方案有 k2 - k1 - 1 个缺陷，如果 k1 = k2，则有 0 个缺陷，如果 k1 > k2，则有 k1 - k2 - 1 个缺陷。 = 的情况很明显。其他的是对称的；少数元素的每个实例最多可以防止总共 k1 + k2 - 1 个可能的缺陷中的两个。

这个贪心算法通过以下逻辑返回最优解。如果前缀(部分解决方案)扩展到最佳解决方案，我们将其称为 safe。显然，空前缀是安全的，如果安全前缀是一个完整的解决方案，那么该解决方案是最优的。足以归纳地表明，每一个贪婪的步骤都保持安全。

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

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

现在假设 P 确实以 y 结尾。通过将第一次出现的 x 移到前面来修改 Q。在此过程中，我们最多引入一个缺陷(x 曾经是)并消除一个缺陷(yy)。

生成所有解决方案

这是tobias_k's answer加上有效的测试来检测当前正在考虑的选择何时以某种方式受到全局约束。渐近运行时间是最优的，因为生成的开销是输出长度的数量级。不幸的是，最坏情况的延迟是二次的。可以通过更好的数据结构将其简化为线性(最优)。

from collections import Counter
from itertools import permutations
from operator import itemgetter
from random import randrange


def 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 == fast


for r in range(10000):
    test([randrange(3) for i in range(randrange(6))])