Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>@Torlack, @Jason Cohen: Recursion is a bad idea here, because there are "overlapping subproblems." I.e., If you choose <code>a</code> as <code>1</code> and <code>b</code> as <code>2</code>, then you have 3 variables left that should add up to 497; you arrive at the same subproblem by choosing <code>a</code> as <code>2</code> and <code>b</code> as <code>1</code>. (The number of such coincidences explodes as the numbers grow.)</p> <p>The traditional way to attack such a problem is <a href="http://en.wikipedia.org/wiki/Dynamic_programming" rel="nofollow noreferrer">dynamic programming</a>: build a table bottom-up of the solutions to the sub-problems (starting with "how many combinations of 1 variable add up to 0?") then building up through iteration (the solution to "how many combinations of <em>n</em> variables add up to <em>k</em>?" is the sum of the solutions to "how many combinations of <em>n-1</em> variables add up to <em>j</em>?" with 0 &lt;= <em>j</em> &lt;= <em>k</em>). </p> <pre><code>public static long getCombos( int n, int sum ) { // tab[i][j] is how many combinations of (i+1) vars add up to j long[][] tab = new long[n][sum+1]; // # of combos of 1 var for any sum is 1 for( int j=0; j &lt; tab[0].length; ++j ) { tab[0][j] = 1; } for( int i=1; i &lt; tab.length; ++i ) { for( int j=0; j &lt; tab[i].length; ++j ) { // # combos of (i+1) vars adding up to j is the sum of the # // of combos of i vars adding up to k, for all 0 &lt;= k &lt;= j // (choosing i vars forces the choice of the (i+1)st). tab[i][j] = 0; for( int k=0; k &lt;= j; ++k ) { tab[i][j] += tab[i-1][k]; } } } return tab[n-1][sum]; } </code></pre> <pre> $ time java Combos 2656615626 real 0m0.151s user 0m0.120s sys 0m0.012s </pre>
    singulars
    1. This table or related slice is empty.
    1. PONumber of possible combinations
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USChris Conway
    1. USChris Conway
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PONumber of possible combinations
      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. VTUpMod
    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. VTUpMod
    1. COYou're right, dynamic programming is best! In my code solution above, I suggest using a cache table of pairs, but there's a LOT of pairs, so DP is better. However I tried to work out the DP solution and it was too hard for little ol' me. :-)
      singulars
      1. PO
      1. USJason Cohen
    2. COActually just summand * sum pairs, so that's not so bad at 5 x 500.
      singulars
      1. PO
      1. USJason Cohen
    3. CO@Chris I'm having problems understanding the meaning of values in the array you build in your solution. Could you please give me some example? In your array tab[2][1]=3 and means "how many combinations of (2+1) vars add up to 1? What are these combinations? (I assume that since they are combinations, the order doesn't matter)
      singulars
      1. PO
      1. USPiotr De
 

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