Как создать перекрестное произведение наборов в определенном порядке - PullRequest
Новая
       25

Как создать перекрестное произведение наборов в определенном порядке

1 голос
/ 01 марта 2011

Учитывая некоторые наборы (или списки) чисел, я хотел бы перебрать перекрестное произведение этих наборов в порядке, определяемом суммой возвращенных чисел. Например, если заданы наборы {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, если есть модули, которые могут помочь.)

1 Ответ

1 голос
/ 01 марта 2011

Для двух наборов A и B мы можем использовать минимальную кучу следующим образом.

  1. Сортировка А.
  2. Сортировка Б.
  3. Переместите (0, 0) в минимальную кучу H с функцией приоритета (i, j) | -> A [i] + B [j]. Разрывай галстуки, предпочитая маленькие я и 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))
...