StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><em>Note: see below why this approach will not give the best results.</em></p> <p>My first approach would be to start off with the special case L={} (which should give the sum of all integers) and add that to a list of solutions. From there add possible attributes as restrictions. In the first iteration, try each attribute in turn and remember those that gave a better result. After that iteration, put the remembered ones into a list of solutions.</p> <p>In the second iteration, try to add another attribute to each of the remembered ones. Remember all those that improved the result. Remove duplicates from the remembered attribute combinations and add these to the list of solutions. Note that {m,n} is the same as {n,m}, so skip redundant combinations in order not to blow up your sets.</p> <p>Repeat the second iterations until there are no more possible attributes that could be added to improve the final sum. If you then order the list of solutions by their sum, you get the requested solution.</p> <p>Note that there are ~20G ways to select three attributes out of 5k, so you can't build a data structure containing those but you must absolutely generate them on demand. Still, the sheer amount can produce lots of temporary solutions, so you have to store those efficiently and perhaps even on disk. You can exploit the fact that you only need the previous iteration's solutions for the next iterations, not the ones before.</p> <p>Another restriction here is that you can end up with less than N best solutions, because all those below L={} are not considered. In that case, I would accept all possible solutions until you have N solutions, and only once you have the N solutions discard those that don't give an improvement over the worst one.</p> <p><strong>Python code</strong>:</p> <pre><code>solutions = [{}] remembered = [{}] while remembered: tmp = remembered remembered = [] for s in remembered: for xs in extensions(s): if score(xs) > score(s) remembered.append(xs) solutions.extend(remembered) </code></pre> <p><strong>Why this doesn't work:</strong></p> <p>Consider a temporary solution consisting of the three records</p> <pre><code>-2, T, F -2, F, T +3, F, F </code></pre> <p>The overall sum of these is -1. When I now select the first attribute, I discard the second and third record, giving a sum of -2. When selecting the second attribute, I discard the first and third, giving the same sum of -2. When selecting both the first and second attribute, I discard all three records, giving a sum of zero, which is an improvement. </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

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