Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Splitting values into groups evenly

Let me try to explain the situation the best I can.

Lets say I have 3 values

1, 2, 3

I tell an algorithm to split this values into x columns. Lets say x = 2 for clarification.

The algorithm determines that the group of values is best put into two columns the following way.

1st column    2nd column
---------------------------
1             3
2

Each column has an even number (totals, not literals) value.

Now lets say I have the following values

7, 8, 3, 1, 4

I tell the algorithm that I want the values split into 3 columns. The algorithm now tells me that the following is the best fit.

1st column    2nd column    3rd column
8             7             3
              1             4

Notice how the columns arent quiet even, but it is as close as it can get. A little over and a little under is considered ok, as long as the list is AS CLOSE TO EVEN AS IT CAN BE.

Anybody got any suggestions? Know any good methods of doing this?

like image 209
Paul Knopf Avatar asked Jun 09 '10 19:06

Paul Knopf


People also ask

How do you split Data equally?

Select the cell, range, or entire column that contains the text values that you want to split. On the Data tab, in the Data Tools group, click Text to Columns. Follow the instructions in the Convert Text to Columns Wizard to specify how you want to divide the text into separate columns.


1 Answers

I would do it like this:

  • add all the values, let's call this S
  • divide S by the number of columns, let's call this M.
  • find a set of values of which the sum is M or as close as possible to M, using a knapsack algorithm (e.g. http://search.cpan.org/~andale/Algorithm-Knapsack-0.02/lib/Algorithm/Knapsack.pm (just a quick Google on knapsack))
  • take the sum of the set of values and subtract it from S, let's call it T.
  • divide T by the number of columns minus 1
  • and repeat the algorithm
like image 181
Patrick Avatar answered Sep 28 '22 10:09

Patrick