python - 以排列值顺序生成多个列表的所有排列

Question

我已经查看了其他几个关于排列的问题，但似乎没有出现这种变体。我正在寻找一种生成有偏排列的简单方法。这就是我的意思。

假设我有两个列表(尽管我需要解决 N 个列表):

l1 = [a, b, c]
l2 = [d, e, f]

这些列表的排列看起来像 [(a,d), (a,e), (a,f), (b,d), (b,e), (b,f) ...] .然而，在我的世界中，排列的元素被评分并相加以评估排列。假设a、d和e值2分，b、c和f 值 1 分。一些样本排列的值是:

(a,d) = 4
(a,e) = 4 
(a,f) = 3
(c,f) = 2

我需要生成所有排列，但我想在生成低值排列之前生成高值排列。

假设每个列表的元素按值降序排列，是否有一种很好的方法来按值顺序生成排列？

(显然我可以生成所有的排列并对它们进行排序，但我更愿意编写一个生成器，因为排列的数量可能很大。)

Answer 1

例如，让 l1={6,4,3,1} 和 l2={5,4,1}。在 2D 平面上将它们绘制为水平线和垂直线。

那么兴趣点都是路口。我们应该报告这些交叉点，以便一条从 (inf, inf) 移动到 (0, 0) 的假想扫描线接触到它们。请注意，位于水平线上的一个点不能比同一条线上的另一个更右的点更早报告。所以对于每条水平线，我们必须只检查最右边的点。从所有这些点中，我们必须选择一个坐标总和最大的点。这可以通过堆数据结构来完成。

最初，我们将位于最右侧垂直线上的所有点放入堆中。然后我们从堆中提取顶点，让出它，最后将它的左邻居放入堆中(如果它有一个)。所以堆总是最多包含 len(l1) 个元素，每个新生成的点都花费 O(log(len(l1)))。如果我们选择 l1 是给定的两个列表中的最小列表，则可以改进解决方案。

这是示例解决方案:

import heapq

a = [("a", 6), ("b", 4), ("c", 3), ("d", 1)]
b = [("e", 5), ("f", 5), ("g", 4), ("h", 2)]

class Pair:
    def __init__(self, i, j, value):
        self.i = i
        self.j = j
        self.value = value
    def __cmp__(self, other):
        return other.value - self.value

def solution(a, b):
    heap = []
    for i in range(len(a)):
        heapq.heappush(heap, Pair(i, 0, a[i][1] + b[0][1]))
    while len(heap) > 0:
        pair = heapq.heappop(heap)
        yield (a[pair.i], b[pair.j], pair.value)
        if pair.j + 1 < len(b):
            heapq.heappush(heap, Pair(pair.i, pair.j + 1, a[pair.i][1] + b[pair.j + 1][1]))

for (a, b, value) in solution(a, b):
    print ("%s %s -> %d" % (a, b, value))

当我们进入更高维度时，情况会变得更糟(要组合的列表超过 2 个)。它可以在二维解决方案之上通过内存来解决，所以我们首先为 l1、l2 构建一个类似于惰性列表的数据结构的答案，然后再次应用相同的算法，为此内存列表和 l3 作为参数，等等。必须采取的最后一步 - 我们应该始终使用长度较小的数组作为 l1，或者在一开始就摆脱将 l1 的所有元素插入堆。

N 个列表的完整代码示例 here , 因为它太长了。