python - 加权元素的笛卡尔积

Question

我有一个元素集合，其中每个元素都附加了一个值(0..1)(实际容器类型并不重要)。我正在迭代笛卡尔积，即元素的组合，其中一个元素取自每一组，如下所示:

import random
import itertools

stuff = [[random.random() for _ in range(random.randint(2,3))] for _ in range(2)]

for combo in itertools.product(*stuff):
    print sum(combo)  # yield in actual application

很简单，但我想首先获得总和值更高的组合。这不需要是确定性的，这足以让我有更高的机会在获得低值(value)组合之前获得高值(value)组合。

是否有一种巧妙的方法可以在不先创建所有组合的情况下执行此操作？也许通过以某种方式排序/移动元素集？

Answer 1

确实有更好的方法来做到这一点，首先按降序对集合进行排序，然后进行迭代，以便我们首先选择每个集合的初始元素。由于它们是经过排序的，这确保了我们通常首先获得高值(value)的组合。

让我们逐步建立直觉，并绘制出结果。我发现这对于理解该方法有很大帮助。

当前方法

首先，您当前的方法(为了清晰起见，进行了轻微编辑)。

import random
import itertools
import matplotlib.pyplot as plt

list1 = [random.random() for _ in range(50)]
list2 = [random.random() for _ in range(50)]

values = []

for combo in itertools.product(list1, list2):
    values.append(sum(combo))
    print(sum(combo))           # yield in actual application

plt.plot(values)
plt.show()

结果是，

到处都是这样的事!我们已经可以通过施加一些排序结构来做得更好。接下来让我们探讨一下。

对列表进行预排序

list1 = [random.random() for _ in range(50)]
list2 = [random.random() for _ in range(50)]

list1.sort(reverse=True)
list2.sort(reverse=True)

for combo in itertools.product(list1, list2):
    print(sum(combo))           # yield in actual application

哪个产量，

看看那个美丽的结构!我们可以利用它来首先产生最大的元素吗？

利用结构

对于这一部分，我们将不得不放弃 itertools.product，因为它对于我们的口味来说太笼统了。类似的函数很容易编写，并且当我们这样做时我们可以利用数据的规律性。我们对图 2 中的峰值了解多少？好吧，由于数据已排序，因此它们必须全部出现在较低的索引处。如果我们将集合的索引想象为一些高维空间，这意味着我们需要更喜欢接近原点的点 - 至少在最初是这样。

下面的二维图支持了我们的直觉，

基于图形的矩阵遍历应该足够了，确保我们每次都移动到一个新元素。现在，我将在下面提供的实现会构建一组已访问的节点，这不是您想要的。幸运的是，所有不在“边界”上的已访问节点(当前可到达但未访问的节点)都可以被删除，这应该会大大限制空间复杂性。我让你想出一个聪明的方法来做到这一点。

代码，

import random
import itertools
import heapq


def neighbours(node):       # see https://stackoverflow.com/a/45618158/4316405
    for relative_index in itertools.product((0, 1), repeat=len(node)):
        yield tuple(i + i_rel for i, i_rel
                    in zip(node, relative_index))


def product(*args):
    heap = [(0, tuple([0] * len(args)))]    # origin
    seen = set()

    while len(heap) != 0:                   # while not empty
        idx_sum, node = heapq.heappop(heap)

        for neighbour in neighbours(node):
            if neighbour in seen:
                continue

            if any(dim == len(arg) for dim, arg in zip(neighbour, args)):
                continue                    # should not go out-of-bounds

            heapq.heappush(heap, (sum(neighbour), neighbour))

            seen.add(neighbour)

            yield [arg[idx] for arg, idx in zip(args, neighbour)]


list1 = [random.random() for _ in range(50)]
list2 = [random.random() for _ in range(50)]

list1.sort(reverse=True)
list2.sort(reverse=True)

for combo in product(list1, list2):
    print(sum(combo))

代码沿着边界行走，每次选择索引总和最低的索引(与原点“接近”的启发式)。这个效果很好，如下图所示，