Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>For two sets A and B, we can use a min heap as follows.</p> <ol> <li>Sort A.</li> <li>Sort B.</li> <li>Push (0, 0) into a min heap H with priority function (i, j) |-> A[i] + B[j]. Break ties preferring small i and j.</li> <li>While H is not empty, pop (i, j), output (A[i], B[j]), insert (i + 1, j) and (i, j + 1) if they exist and don't already belong to H.</li> </ol> <p>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).</p> <hr> <p>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.</p> <pre><code>from heapq import heappop, heappush def largest_to_smallest(lists): """ &gt;&gt;&gt; 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] &gt;= 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)) </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POHow to generate cross product of sets in specific order
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USuser635541
    1. USuser635541
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POHow to generate cross product of sets in specific order
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTDownMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. COThanks, that looks promising! Could you give me a pointer for "the naive algorithm and sort to get down to two sets"?
      singulars
      1. PO
      1. USdiagonallemma
    2. COIf you want A x B x C x D, then compute A x B, sort it, compute C x D, sort it, and then compute (A x B) x (C x D).
      singulars
      1. PO
      1. USuser635541
    3. COTo minimize space usage, you should group the sets so that the naively computed Cartesian products are about the same size.
      singulars
      1. PO
      1. USuser635541
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload