加权元素的笛卡尔积

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

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

有没有不用先创建所有组合就可以做到这一点的巧妙方法？也许通过 sorting/shifting 以某种方式设置元素？

Answer 1

确实有更好的方法来做到这一点，首先按降序对集合进行排序，然后迭代，这样我们 select 首先是每个集合的初始元素。由于它们已排序，这确保我们通常首先获得高价值组合。

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

当前方法

首先，您当前的方法（为清楚起见略作编辑）。

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 中的峰值了解多少？好吧，由于数据是排序的，它们必须都出现在较低的索引处。如果我们将集合的索引想象成一些更高维的 space，这意味着我们需要更喜欢靠近原点的点 - 至少在最初是这样。

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

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

代码，

import random
import itertools
import heapq


def neighbours(node):       # see 
    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))

代码沿着边界走，每次select使用索引总和最低的索引（'closeness' 到原点的启发式）。这样效果很好，如下图所示，

Answer 2

受 N. Wouda 的回答启发，我尝试了另一种方法。在测试他们的答案时，我注意到索引中有一个类似于 n 元编码的模式（这里有 3 组）：

...
(1,1,0)
(1,1,1)
(0,0,2)
(0,1,2)
(1,0,2) <- !
(1,1,2)
(0,2,0)
(0,2,1)
(1,2,0)
...

请注意，较低的数字先于较高的数字增加。所以我在代码中复制了这个模式：

idx = np.zeros((len(args)), dtype=np.int)
while max(idx) < 50:  # TODO stop condition
    yield [arg[i] for arg,i in zip(args,idx)]

    low = np.min(idx)
    imin = np.argwhere(idx == low)
    inxt = np.argwhere(idx == low+1)

    idx[imin[:-1]] = 0  # everything to the left of imin[-1]
    idx[imin[-1]] += 1  # increase the last of the lowest indices
    idx[inxt[inxt > imin[-1]]] = 0  # everything to the right

因为我只是在测试，所以我走了一些捷径；结果还不错。虽然一开始这个函数优于 N. Wouda 的解决方案，但它运行的时间越长，情况就越糟。我认为 "index-wave" 的形状不同，导致离原点越远的指数噪声越大。

有意思！

编辑我觉得这很有趣，所以我想像了索引迭代的方式 - JFYI :)

指数波前 N. Wouda

来自这个答案的指数波前

加权元素的笛卡尔积

Cartesian Product of Weighted Elements

python

heuristics

cartesian-product

当前方法

预排序列表

利用结构