Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>From <a href="http://en.wikipedia.org/wiki/Set_cover_problem" rel="nofollow">Set Cover Problem</a></p> <blockquote> <p>The greedy algorithm for set covering chooses sets according to one rule: at each stage, choose the set that contains the largest number of uncovered elements</p> </blockquote> <p>Wikipedia seems to say that this algorithm works the best under plausible complexity assumptions.</p> <p>I would boil it down to these steps:</p> <ol> <li>Pick an element from the list (the first one, probably)</li> <li>Pick the next element you come across where all 5 numbers are not yet represented in the sub-list</li> <li>If you reach the end, go back to the beginning of the list and lower the criteria of step #2 to 4 numbers</li> <li>Repeat steps 2 &amp; 3 until you have covered all integers</li> </ol> <p>Depending on the programming language you're using, there are ways of making this pretty quick.</p> <p><strong>Edit: the poster has explained that each integer must be used <em>exactly</em> once</strong></p> <p>So, what you really need to do is just continue adding elements until the element contains an integer that is already present in your subset. The "exactly" criterion takes precedent over the "not yet in the subset" criterion. You'll break out of the loop when you hit 120 subsets.</p> <p>You may also want to keep track of the order in which you add elements to your subset, and when you hit a dead end (e.g., each of the elements remaining in the superset contains an integer that is already present in your subset) you backtrack one element and continue.</p> <p>In order to backtrack and remember what combinations do not work, you will need to keep a list of "banned collections", and each time you decide whether to add a new element you should first make sure it's not in this list of banned collections. The best way (that I've found) to do this in Ruby is to store the Hash of the collection rather than the collection itself. This provides an inexpensive way to evaluate whether the prospective collection has already been tried and has led to a dead-end.</p> <p>Good luck!</p>
    singulars
    1. This table or related slice is empty.
    1. PONeed algorithm for choosing sets of integer from list of such sets
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USacsmith
    1. USacsmith
    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
    1. COJust thinking -- you may want to revise step #2 to "skip elements while the element contains a number that is already represented in the sublist," as this may be more efficient.
      singulars
      1. PO
      1. USacsmith
    2. COI must be misunderstanding you. As soon as I go to step 2, it seems to me, I begin to accept sets containing an element that's already been covered: I need to cover the 600 in such a way that no integer in the range is used more than once. I think that if I begin in the fashion above, I'll need a way to remove sets as well as just accumulating them.
      singulars
      1. PO
      1. USthelma
    3. COAh, okay. Well, that's more difficult, because there's the possibility that a solution does not exist – but you would have to exhaust all possible combinations to find that out.
      singulars
      1. PO
      1. USacsmith
 

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