Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>This is what I call a "sort and bracket" problem. The way you solve it is by sorting the data and then bracketing around the target value or target range.</p> <p>For example, in this case the sorted order is:</p> <p>98<br> 112<br> 126<br> 182<br> 191<br> 196<br> 210<br> 213<br> 223<br> 237<br></p> <p>Now you average the list: 178.8. Therefore the starting bracket is (126,182). Start moving out from this average: sum(126,182,112,191,98) = 709, too small. Delete the 98 and replace with value from the other side: 196, ie sum(126,182,112,191,196) = 807, still too small. Go to next value on high side, sum(126,182,112,191,210)=821. Ok, found one match. By continuing this process you can find every match. Basically what bracketing does is help you search only a subset of all the possible combinations so you do not have to check every combination. You are generating combinations outward from an average, instead of from one end or the other.</p> <p>Whenever your sum exceeds/falls below the range you terminate the combination generation on the high/low side and switch to the other. This is the optimal solution to the problem.</p> <p>Implementation Method: to implement this algorithm you need to get a combination generator that works in "lexicographical" order. You then start with n, say 5, items and determine the median combination as I have shown above. You then get the next lower combination, if you are low, you switch to the next higher combination and so on.</p> <p>-------------- ADDENDUM -------------------</p> <p>After thinking about this it might be better to use a plain changes-type algorithm for this rather than a lexicographical combinator. This type of algorithm will generate all combinations, but only switch any 2 elements at a given time. Basically you modify this algorithm to switch direction whenever it goes out of bounds (goes above the range or below it).</p>
    singulars
    1. This table or related slice is empty.
    1. POAlgorithm: Extract subset based on property sum
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USTyler Durden
    1. USTyler Durden
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    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. COThis is certainly a different (and more programmer-y) way to attack the problem. After reading through 'standard' implementations of of the subset-sum problem, your solution struck me as insufficient at first, but the more I think about how it needs to work, the more I like it. It has great speed potential, as it will weight itself very well middle of the curve to the specifics of my data set (especially if I'm able to guess the # of items correctly from the outset). Biggest drawback is that the code required to implement this may be... obtuse to anyone other than the implementor. : )
      singulars
      1. PO
      1. USJohn Green
    2. COThis isn't the optimal solution to the problem. It works well for a particular subset of the possible inputs but has bad performance for others.
      singulars
      1. PO
      1. USargentage
 

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