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

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[i] + B[j]。打破平局更喜欢小的 i 和 j。
4. 当H不为空时，弹出(i, j)，输出(A[i], B[j])，插入(i + 1, j)和(i, j + 1)如果存在'已经属于 H。

对于两个以上的集合，使用朴素算法并排序以得到两个集合。在最好的情况下(当每个集合相对较小时发生)，这需要存储 O(√#tuples) 个元组而不是 Ω(#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))