StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><strong>Step 1: Calculate pair differences</strong></p> <p>I think it is fairly obvious that the right approach is to sort the numbers and then take differences between each adjacent pair of numbers. These differences are the "candidate" differences contributing to the minimal difference sum. Using the numbers from your example would lead to:</p> <pre><code>Number Diff ====== ==== 1561 11 1572 0 1572 37 1609 73 1682 49 1731 0 1731 310 2041 </code></pre> <p>Save the differences into an array or table or some other data structure where you can maintain the differences and the two numbers that contributed to each difference. Call this the <code>DiffTable</code>. It should look something like:</p> <pre><code>Index Diff Number1 Number2 ===== ==== ======= ======= 1 11 1561 1572 2 0 1572 1572 3 37 1572 1609 4 73 1609 1682 5 49 1682 1731 6 0 1731 1731 7 310 1731 2041 </code></pre> <p><strong>Step 2: Choose minimal Differences</strong></p> <p>If all numbers had to be chosen, we could have stopped at step 1 by choosing the number pair for odd numbered indices: 1, 3, 5, 7. This is the correct answer. However, the problem states that a subset of pairs are chosen and this complicates the problem quite a bit. In your example 3 differences (6 numbers = 3 pairs = 3 differences) need to be chosen such that:</p> <ul> <li>The sum of the differences is minimal</li> <li>The numbers participating in any chosen difference are removed from the list.</li> </ul> <p>The second point means that if we chose <code>Diff</code> <code>11</code> (Index = 1 above), the numbers <code>1561</code> and <code>1572</code> are removed from the list, and consequently, the next <code>Diff</code> of <code>0</code> at index 2 cannot be used because only 1 instance of <code>1572</code> is left. Whenever a <code>Diff</code> is chosen the adjacent <code>Diff</code> values are removed. This is why there is only one way to choose 4 pairs of numbers from a list containing eight numbers.</p> <p>About the only method I can think of to minimize the sum of the <code>Diff</code> above is to generate and test.</p> <p>The following pseudo code outlines a process to generate all 'legal' sets of index values for a <code>DiffTable</code> of arbitrary size where an arbitrary number of number pairs are chosen. One (or more) of the generated index sets will contain the indices into the <code>DiffTable</code> yielding a minimum <code>Diff</code> sum. </p> <pre><code>/* Global Variables */ M = 7 /* Number of candidate pair differences in DiffTable */ N = 3 /* Number of indices in each candidate pair set (3 pairs of numbers) */ AllSets = [] /* Set of candidate index sets (set of sets) */ call GenIdxSet(1, []) /* Call generator with seed values */ /* AllSets now contains candidate index sets to perform min sum tests on */ end procedure: GenIdxSet(i, IdxSet) /* Generate all the valid index values for current level */ /* and subsequent levels until a complete index set is generated */ do while i <= M if CountMembers(IdxSet) = N - 1 then /* Set is complete */ AllSets = AppendToSet(AllSets, AppendToSet(IdxSet, i)) else /* Add another index */ call GenIdxSet(i + 2, AppendToSet(IdxSet, i)) i = i + 1 end return </code></pre> <p>Function <code>CountMembers</code> returns the number of members in the given set, function <code>AppendToSet</code> returns a new set where the arguments are appended into a single ordered set. For example <code>AppendToSet([a, b, c], d)</code> returns the set: <code>[a, b, c, d]</code>.</p> <p>For the given parameters, M = 7 and N = 3, AllSets becomes:</p> <pre><code>[[1 3 5] [1 3 6] <= Diffs = (11 + 37 + 0) = 48 [1 3 7] [1 4 6] [1 4 7] [1 5 7] [2 4 6] [2 4 7] [2 5 7] [3 5 7]] </code></pre> <p>Calculate the sums using each set of indices, the one that is minimum identifies the required number pairs in <code>DiffTable</code>. Above I show that the second set of indices gives the minimum you are looking for.</p> <p>This is a simple brute force technique and it does not scale very well. If you had a list of 50 number pairs and wanted to choose the 5 pairs, AllSets would contain 1,221,759 sets of number pairs to test.</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