Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>This is an interesting problem. I will use your example dividing the numbers 1..10 into three groups to illustrate my answer. The solution will apply to any set of numbers and any number of groups. Of sourse, when the size of the set of numbers is large you may not be able to use a brute force approach. Having said that, large sets of numbers can be handled in a similar way but more on that later.</p> <p>Lets say we have M consecutive numbers, denoted (1..M), in the set and we want to divide these into N groups.</p> <p>The first thing to determine is the value that you will compare the sum of each group to. This is simply the sum of the set of numbers divided by the the number of groups N. </p> <p>In the example sumOf(1..M) = 55 and N = 3 so 55/3 = 18.33 is the value that each group should sum to. You want to minimise the difference between the group sums and 18.33</p> <p>As another example, if you want to divide the set of numbers 1..20 into two groups then you will want to minimise the difference between the group sums and sumOf(1..20) = 210 divide by 2 groups = 210/2 = 105.</p> <p>The next step is to find all possible groups. This is another interesting problem nad given the restriction of proups containing consecutive numbers, the total number of groups combinations is not as many as you might expect.</p> <p>Finding the combinations is a recursive problem and it is easy enough to work out a general equation. </p> <p>lets start with a simple case. How many combinations of 10 numbers in the set (1..10). Well, there is only one group, the numbers (1..10)</p> <p>Now, how many combinations of 2 groups in the 10 numbers. The answer is M-1 or 10-1 = 9, namely</p> <pre><code>(1),(2..10) (1..2) (3..10) (1..3) (4..10) (1..4) (5..10) (1..5) (6..10) (1..6) (7..10) (1..7) (8..10) (1..8) (9..10) (1..9) (10) </code></pre> <p>So a set of size M has M-1 combinations of groups. This is the basis of the recursion.</p> <p>How many combinations of 3 groups in the 10 numbers.</p> <p>Well, the first group will be one of the following</p> <pre><code>(1),(1..2),(1..3) ,(1..4) ,(1..5),(1..6) ,(1..7) ,(1..8) </code></pre> <p>Given any of these as the first group, lets work out how many combinations of 2 groups exist in the remaining numbers.</p> <p>Let the first group of the three = (1). We have nine numbers left and know these can make 9-1 = 8 different combinations of 2 groups Let the first group of the three = (1..5). We have five numbers left and these can make 5-1 = 4 different groups of 2 numbers.</p> <p>So, in total we will have</p> <pre><code>(1) -&gt; 8 combinations (1..2) -&gt; 7 combinations (1..3) -&gt; 6 combinations (1..4) -&gt; 5 combinations (1..5) -&gt; 4 combinations (1..6) -&gt; 3 combinations (1..7) -&gt; 2 combinations (1..8) -&gt; 1 combinations </code></pre> <p>giving SumOf(1..8) ,or in general (sum(1..M-2), combinations of groups. SumOf(1..8) = 8*9/2 = 36</p> <p>So there are 36 combinations of 3 groups in 10 numbers where each group contains consecutive numbers.</p> <p>as an aside, for 3 groups in 100 numbers you have sumOf(1..98) = 98*99/2 = 4851 combinations of groups, so as M increases you will get more combinations and as some value of M the brute force method may not be possible.</p> <p>The approach outlined above can be used to design a simple recursive algorithm to get all combinations of groups in the set (1..M).</p> <p>Also, a simple equation can be worked out for any number N of groups in a set of M numbers. For example, if you move to 4 groups in 10 numbers then you have situations like first group is (1..3), then find combinations of 3 groups in the remaining 7 nuumbers. There will be sum(1..M-2) = sum(1..5)..etc. </p> <p>Anyway, back to the problem. You have all combinations of groups and so you can iterate through the groups and calculate the SAD for each combination and choose the one that minimises the SAD.</p> <p>When the number of combinations is very large and you can't look at each combination then you could try bootstrapping to select groups at random or some kind of evolutionary algorithm approach where you start with a number of randomly chosen combinations and then randomly move numbers from one group to another and keep those that have the lowest SAD. Continue this step until you see no further improvement in SAD. </p> <p>Or you might do as @Robert King suggested, starting out with a single combination and improving on it by moving numbers from one group to another. </p>
    singulars
    1. This table or related slice is empty.
    1. POHow to divide a line of numbers into N groups such that the sums of each group are closest to their mean?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USmartino
    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. This table or related slice is empty.
    1. This table or related slice is empty.
 

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