生成一个列表，而不相邻相等元素的所有排列 [英] Generate all permutations of a list without adjacent equal elements

问题描述

当我们对列表排序，如

a = [1,2,3,3,2,2,1]
sorted(a) => [1, 1, 2, 2, 2, 3, 3]

等于元素总是在结果列表中相邻。

equal elements are always adjacent in the resulting list.

我怎样才能达到相反的任务 - 洗牌的列表，以便平等的要素是从来没有（或尽可能少）相邻

How can I achieve the opposite task - shuffle the list so that equal elements are never (or as seldom as possible) adjacent?

例如，对于上面所列的可能的解决方案之一是

For example, for the above list one of the possible solutions is

p = [1,3,2,3,2,1,2]

更正式地说，给定一个列表 A ，生成一个置换 P 它最小化对数 P [I] == P [I + 1] 。

More formally, given a list a, generate a permutation p of it that minimizes the number of pairs p[i]==p[i+1].

由于列表是大的，产生和筛选所有排列不是一个选项。

Since the lists are large, generating and filtering all permutations is not an option.

奖金的问题：如何有效地生成所有这样的排列

Bonus question: how to generate all such permutations efficiently?

这是在code我使用的测试解决方案：<一href="https://gist.github.com/gebrkn/9f550094b3d24a35aebd">https://gist.github.com/gebrkn/9f550094b3d24a35aebd

This is the code I'm using to test the solutions: https://gist.github.com/gebrkn/9f550094b3d24a35aebd

UPD：在这里选择一个获胜者是一个艰难的选择，因为很多人贴出优秀的答案。 @Heuster ， @大卫Eisenstat ， @Coady ，的 @ enrico.bacis 和 @srgerg 规定，产生最佳的排列完美的功能。 @tobias_k 和大卫还回答了奖金问题（生成所有排列）。附加分，大卫的正确性证明。

UPD: Choosing a winner here was a tough choice, because many people posted excellent answers. @Heuster, @David Eisenstat, @Coady, @enrico.bacis and @srgerg provided functions that generate the best possible permutation flawlessly. @tobias_k and David also answered the bonus question (generate all permutations). Additional points to David for the correctness proof.

从@Heuster的code似乎是最快的。

The code from @Heuster appears to be the fastest.

推荐答案

这是沿Thijser的目前尚不完整伪code线。我们的想法是把最频繁的其余项目类型，除非它是刚刚拍摄。 （参见该算法的科迪的实施。）

This is along the lines of Thijser's currently incomplete pseudocode. The idea is to take the most frequent of the remaining item types unless it was just taken. (See also Coady's implementation of this algorithm.)

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，最佳的解决方案具有K2 - K1 - 1的缺陷，如果K1＆LT; K2，如果0缺陷K1 = K2和K1 - K2 - 1的缺陷，如果K1> K2。的情况下=是显而易见的。其他是对称的; 1可能

Proof of correctness

For two item types, with counts k1 and k2, the optimal solution has k2 - k1 - 1 defects if k1 < k2, 0 defects if k1 = k2, and k1 - k2 - 1 defects if k1 > k2. The = case is obvious. The others are symmetric; each instance of the minority element prevents at most two defects out of a total of k1 + k2 - 1 possible.

此贪心算法返回最优解，由以下逻辑。我们所说的preFIX（局部的溶液）的安全的，如果它延伸到一个最佳的解决方案。显然，空preFIX是安全的，并且如果安全preFIX是一个整体解决方案则该解决方案是最佳的。它足以感应显示，每个贪婪一步保持安全。

This greedy algorithm returns optimal solutions, by the following logic. We call a prefix (partial solution) safe if it extends to an optimal solution. Clearly the empty prefix is safe, and if a safe prefix is a whole solution then that solution is optimal. It suffices to show inductively that each greedy step maintains safety.

这是一个贪婪的一步引入了缺陷的唯一方法是如果只有一个项目类型仍然存在，在这种情况下，只有一个办法继续下去，而这种方式是安全的。否则，设P为（安全）$ P $只是考虑中的步骤之前PFIX，让P'刚过是preFIX，并让S为延伸P.的最佳解决方案若S延伸P'也，则做完了。否则，令P'= Px的和S = PQ及Q = YQ'，其中x和y是物品和Q和Q'是这样的序列

The only way that a greedy step introduces a defect is if only one item type remains, in which case there is only one way to continue, and that way is safe. Otherwise, let P be the (safe) prefix just before the step under consideration, let P' be the prefix just after, and let S be an optimal solution extending P. If S extends P' also, then we're done. Otherwise, let P' = Px and S = PQ and Q = yQ', where x and y are items and Q and Q' are sequences.

首先假设P没有与y结尾。由算法的选择，x至少为频繁Q中为y。考虑的Q仅含有x和y的最大串。如果第一子串具有至少一样多X的为y的，那么就可以不引入额外的缺陷，以开始随x重写。如果第一个字符串有多个Y比X的，那么其他一些子已经有X的除Y的，所以使得x先走，我们可以重写这些子没有额外的缺陷。在这两种情况下，我们发现最佳方案Ť即根据需要延伸P'

Suppose first that P does not end with y. By the algorithm's choice, x is at least as frequent in Q as y. Consider the maximal substrings of Q containing only x and y. If the first substring has at least as many x's as y's, then it can be rewritten without introducing additional defects to begin with x. If the first substring has more y's than x's, then some other substring has more x's than y's, and we can rewrite these substrings without additional defects so that x goes first. In both cases, we find an optimal solution T that extends P', as needed.

现在假设p还与y结尾。通过移动x的第一次出现在前面修改Q值。在这样做时，我们引入至多一个缺陷（其中x曾经是），并消除一个缺陷（在日）。

Suppose now that P does end with y. Modify Q by moving the first occurrence of x to the front. In doing so, we introduce at most one defect (where x used to be) and eliminate one defect (the yy).

这是 tobias_k的回答加上高效的测试，以检测目前所考虑的选择是在全球范围的限制以某种方式。渐近运行时间是最佳的，因为产生的开销是输出的长度的顺序上。最坏情况下的延迟不幸的是，二次;它可以减少到线性（最佳）具有更好的数据结构

This is tobias_k's answer plus efficient tests to detect when the choice currently under consideration is globally constrained in some way. The asymptotic running time is optimal, since the overhead of generation is on the order of the length of the output. The worst-case delay unfortunately is quadratic; it could be reduced to linear (optimal) with better data structures.

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

这篇关于生成一个列表，而不相邻相等元素的所有排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！