如何按特定順序生成集合的交叉積

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))