특정 순서로 집합의 교차 곱을 생성하는 방법

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>

내가 할 수있는 너무 많은 방법이 있기 때문에 우선 모든 교차 제품을 먼저 계산 한 다음 정렬하십시오. 이터레이터로 이것을 달성하는 영리한 방법이 있습니까?

는 두 세트 A에 대한

Answer 1

(I이 펄을 사용하고, 경우에. 도움이 모듈이 있습니다) 다음과 같이 B, 우리는 분 힙을 사용할 수 있습니다. > A [I] + B [J] - | 우선 순위 기능 (I, J)와 최소 힙 H로

1. 정렬 A.
2. 정렬 B.
3. 푸시 (0, 0). 작은 i와 j를 선호하는 관계를 끊으십시오.
4. H가 존재하지 않으면 pop (i, j), output (A [i], B [j]), insert (i + 1, j) 및 (i, j + 1) 이미 H에 속해 있습니다.

두 세트 이상인 경우 순진한 알고리즘을 사용하고 정렬하여 두 세트를 가져옵니다. 가장 좋은 경우 (각 집합이 비교적 작을 때 발생 함)에는 Ω (# 튜플) 대신 O (√ # 튜플) 튜플에 대한 저장소가 필요합니다.

---

여기에 약간의 파이썬이 있습니다. 그것은 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))