数组的有序笛卡尔积

Question

在两个有序整数数组的高效有序笛卡尔积中，提出了一种生成有序笛卡尔积的惰性算法。

我很想知道这个算法是否可以推广到更多的数组。

例如我们有5个双精度数组

(0.7, 0.2, 0.1)

(0.6, 0.3, 0.1)

(0.5, 0.25, 0.25)

(0.4, 0.35, 0.25)

(0.35, 0.35, 0.3)

我感兴趣的是生成有序的笛卡尔积，而不必计算所有可能的组合。

如果你有什么想法可以将一个可能的懒笛卡尔积算法扩展到2维以上

Answer 1

这个问题似乎是uniform-cost-search的枚举实例(参见示例https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)。状态空间是由指向已排序数组的当前索引集定义的。后继函数是每个数组可能的索引增量的枚举。对于给定的5个数组的示例，初始状态为(0,0,0,0,0)。

没有目标状态检查函数，因为我们需要遍历所有可能性。如果所有输入数组都已排序，则保证结果已排序。

假设我们有m个长度为n的数组，则此方法的复杂度为O((n^m).log(n(m-1))。

下面是一个python的示例实现:

from heapq import heappush, heappop
def cost(s, lists):
    prod = 1
    for ith, x in zip(s, lists):
        prod *= x[ith]
    return prod
def successor(s, lists):
    successors = []
    for k, (i, x) in enumerate(zip(s, lists)):
        if i < len(x) - 1: 
            t = list(s)
            t[k] += 1
            successors.append(tuple(t))
    return successors
def sorted_product(initial_state, lists):    
    fringe = []
    explored = set()
    heappush(fringe, (-cost(initial_state, lists), initial_state))
    while fringe:
        best = heappop(fringe)[1]
        yield best
        for s in successor(best, lists):
            if s not in explored:
                heappush(fringe, (-cost(s, lists), s))
                explored.add(s)
if __name__ == '__main__':
    lists = ((0.7, 0.2, 0.1),
             (0.6, 0.3, 0.1),
             (0.5, 0.25, 0.25),
             (0.4, 0.35, 0.25),
             (0.35, 0.35, 0.3))
    init_state = tuple([0]*len(lists))
    for s in sorted_product(init_state, lists):
        s_output = [x[i] for i, x in zip(s, lists)]
        v = cost(s, lists)
        print '%s %s t%s' % (s, s_output, cost(s, lists))

Answer 2

所以，如果你有A(A1，…， a)和B(B)，…Bn)。

& lt;B当且仅当

A1 *…* An

相关内容

• 没有找到相关文章