如何生成的集特定的顺序积 [英] How to generate cross product of sets in specific order

问题描述

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

Given some sets (or lists) of numbers, I would like to iterate through the cross product of these sets in the order determined by the sum of the returned numbers. For example, if the given sets are { 1,2,3 }, { 2,4 }, { 5 }, then I would like to retrieve the cross-products in the order

＆LT; 3,4,5>， ＆LT; 2,4,5>， ＆LT; -3,2,5->或LT; 1,4,5>， ＆LT; 2,2,5>， ＆LT; 1,2,5>

<3,4,5>, <2,4,5>, <3,2,5> or <1,4,5>, <2,2,5>, <1,2,5>

我不能计算所有交叉的产品，然后再对其进行排序，因为有太多的。有没有什么聪明的办法有一个迭代器实现这一目标？

I can't compute all the cross-products first and then sort them, because there are way too many. Is there any clever way to achieve this with an iterator?

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

(I'm using Perl for this, in case there are modules that would help.)

推荐答案

有关二套A和B，我们可以用最小堆如下：

For two sets A and B, we can use a min heap as follows.

1. 排序。
2. 排序B点。
3. 推送（0，0）到最小堆高带优先功能（I，J）| - > A [I] + B [J]。打破平局preferring小i和j。
4. 虽然H不是空的，流行（I，J），输出（A [1]，B [j]的），插入第（i + 1，j）和（I，J + 1）如果它们存在和唐T已经属于小时。

有关二套以上，用天真的算法和排序趴下两套。在最好的情况下（这发生在每一套相对较小），这需要存储O（√＃元组）的元组，而不是Ω（#tuples）。

For more than two sets, use the naive algorithm and sort to get down to two sets. In the best case (which happens when each set is relatively small), this requires storage for O(√#tuples) tuples instead of Ω(#tuples).

下面是一些Python做到这一点。它应该音译相当直截了当给Perl。你需要从CPAN堆库和我的元组转换为字符串，使他们可以在一个Perl哈希键。该组可以被存储作为哈希以及

Here's some Python to do this. It should transliterate reasonably straightforwardly to Perl. You'll need a heap library from CPAN and to convert my tuples to strings so that they can be keys in a Perl hash. The set can be stored as a hash as well.

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

这篇关于如何生成的集特定的顺序积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！