Databases
StackOverflow2013
Postsdbo
POIterating over pairs of numbers in an increasing order
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POIterating over pairs of numbers in an increasing order
    primarykey
    data
    text
    <p>I'll explain where the question comes from at the bottom, but here's the statement. Suppose I have two lists of non-negative integers, which I'll write <code>(A[0] ... A[n])</code> and <code>(B[0] ... B[m])</code>. They are strictly increasing, so <code>A[i+1] &gt; A[i]</code> for all <code>i</code> and similarly for <code>B</code>. I want to collect all <code>n * m</code> pairs of elements in increasing order of their sum.</p> <p>So, for example if <code>A = (0 1 2)</code> and <code>B = (1 4)</code>, then I want to end up collecting <code>((0 1) (1 1) (2 1) (0 4) (1 4) (2 4))</code>. If there is a tie, I don't care which order I collect the two elements in. For example, if <code>A = (0 1)</code> and <code>B = (0 1)</code>, then I don't mind which of the mixed terms, <code>(0 1)</code> or <code>(1 0)</code>, I pick up first.</p> <p>Obviously, I'd like this to be reasonably efficient. I hope that it's possible in time asymptotic to <code>m * n</code>. Specifically, I'm hoping that the ordered input makes this problem strictly easier than the equivalent problem if I didn't know anything about the inputs. What I was thinking about when I first asked the question was the amount of state we have to store. I was hoping it was possible with a constant amount, but maybe this is unrealistic. (The things I've tried since have all failed!)</p> <p>The code will actually be written in Lisp, but I think that the problem statement is pretty much independent of that. The inputs would most naturally come as singly-linked lists, but I will have to reverse them in advance anyway, so if random-access is relevant, I can make them arrays. In case it's relevant, I expect this to be mostly called on quite small lists, so a massive constant term / constant factor in runtime probably precludes a solution. (Although I'd be fascinated to hear about the algorithm idea!)</p> <p>The background: I've been looking at the source code for Maxima, a computer algebra system and in particular at its code for the multiplication of two polynomials. Polynomials are represented in a "sparse format", so <code>x^5 + x^2 + 2</code> might appear as <code>(5 1 2 1 0 2)</code>, with descending exponents followed by their respective coefficients. To compute the product efficiently, what I really want to do is to collect together the degree zero terms, then the degree 1 terms etc. The current code avoids solving this problem by making a half-hearted stab at it for efficiency, then doing a sort of generic polynomial addition to deal with coefficients in an order it doesn't expect. I feel like we should be able to do better!</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USDavid Eisenstat
    1. USRupert Swarbrick
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POIterating over pairs of numbers in an increasing order
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POIterating over pairs of numbers in an increasing order
      1. USRupert Swarbrick
      1. VTBountyStart
    3. VO
      singulars
      1. POIterating over pairs of numbers in an increasing order
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWhat language are you using? How large are the arrays?
      singulars
      1. POIterating over pairs of numbers in an increasing order
      1. USBohemian
    2. COBohemian: Read the second paragraph. And the others too, if you are trying to answer the question, I guess.
      singulars
      1. POIterating over pairs of numbers in an increasing order
      1. USRupert Swarbrick
    3. COAs a couple of people have pointed out below, I was being dopey when I said "iterating over each list once". I'll make an edit so the statement is a bit more sensible above.
      singulars
      1. POIterating over pairs of numbers in an increasing order
      1. USRupert Swarbrick
 

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