在 efficient sorted Cartesian product of 2 sorted array of integers建议使用惰性算法为两个已排序的整数数组生成有序的笛卡尔积。
我很想知道这个算法是否可以推广到更多的数组。
例如,假设我们有 5 个已排序的 double 数组
(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 以上的维度的任何想法。
最佳答案
这个问题似乎是一个统一成本搜索的枚举实例(参见例如 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))
关于arrays - 数组的有序笛卡尔积,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25391423/