如何按特定顺序生成集合的交叉积

Question

给定一些数字集（或列表），我想按照由返回的数字总和确定的顺序遍历这些集合的叉积。例如，如果给定的集合是{1,2,3}，{2,4}，{5}，那么我想要按顺序检索交叉产品

< 3,4,5> ， < 2,4,5->， < -3,2,5->或< 1,4,5>， < 2,2,5->， < 1,2,5->

我可以首先计算所有的交叉产品，然后对它们进行分类，因为有太多的方法。有没有什么聪明的方法来实现这个迭代器？

（我使用Perl此，万一有模块，这将有助于。）

Answer 1

对于两组A和B，我们可以按如下方式使用最小堆。

1. 排序A.
2. 排序B.
3. 推送（0，0）与优先功能（I，J）最小堆H | - > A [1] + B [j]的。休息关系喜欢小i和j。
4. 虽然H不为空，但pop（i，j），output（A [i]，B [j]），insert（i + 1，j）和（i，j + 1）已经属于H.

对于两个以上的集合，使用朴素算法并进行排序以得到两个集合。在最好的情况下（发生在每个集合相对较小时），这需要存储O（√＃元组）元组而不是Ω（#tuples）。

---

这是一些Python来做到这一点。它应该合理简明地转录到Perl。你需要一个来自CPAN的堆库，并将我的元组转换为字符串，以便它们可以是Perl哈希中的键。该集合也可以作为散列来存储。

from heapq import heappop, heappush 

def largest_to_smallest(lists): 
    """ 
    >>> print list(largest_to_smallest([[1, 2, 3], [2, 4], [5]])) 
    [(3, 4, 5), (2, 4, 5), (3, 2, 5), (1, 4, 5), (2, 2, 5), (1, 2, 5)] 
    """ 
    for lst in lists: 
    lst.sort(reverse=True) 
    num_lists = len(lists) 
    index_tuples_in_heap = set() 
    min_heap = [] 
    def insert(index_tuple): 
    if index_tuple in index_tuples_in_heap: 
     return 
    index_tuples_in_heap.add(index_tuple) 
    minus_sum = 0 # compute -sum because it's a min heap, not a max heap 
    for i in xrange(num_lists): # 0, ..., num_lists - 1 
     if index_tuple[i] >= len(lists[i]): 
     return 
     minus_sum -= lists[i][index_tuple[i]] 
    heappush(min_heap, (minus_sum, index_tuple)) 
    insert((0,) * num_lists) 
    while min_heap: 
    minus_sum, index_tuple = heappop(min_heap) 
    elements = [] 
    for i in xrange(num_lists): 
     elements.append(lists[i][index_tuple[i]]) 
    yield tuple(elements) # this is where the tuple is returned 
    for i in xrange(num_lists): 
     neighbor = [] 
     for j in xrange(num_lists): 
     if i == j: 
      neighbor.append(index_tuple[j] + 1) 
     else: 
      neighbor.append(index_tuple[j]) 
     insert(tuple(neighbor))