Sort/ order numbers over a set amount of columns to optermise the overall height

Question

0.00/5 (No votes)

See more:

Hi,
This is difficult one to explain but here goes. I have a list of numbers which are to be set over a set number of column (Pre-determined by another calulation). The task it to move the number around till the shortest column height (Numbers are additionalised in each column to give height).

I told you it was not going to be easy to explain.

What is the best way to process this to get the column lists?

Ex:- Numbers (232,277,432,200,200,220,500,490,286,478) & Column Count is 4 (Note:- Not always are they evenly balanced by quantity).

Think of it as you can move the numbers from column to column but the aim to to get the lowest average of the sum of the column across all columns.

Ideal would (Not as per example):- Col=200,300,300 Col2=200, 400, 100, 50 Col3= 200, 300, 200 Col4=300, 200, 50, 200

Column sum
Col1=800
Col2=750
Col3=700
Col4= 750

i.e. move the lengths around to make the shortest column.

Thanks in advance.

OK, Realtime numbers
432
432
432
305
205
205
205
205
205
205
150
150
150

4 columns/pots (making an target 820 per each pot)

I hope this helps

What I have tried:

Sorry I have no trys to show as I must confess I don't realy know where to start (Any pointer are welcome).

New Try,
1) Order list to larger -> Smaller
2) Workout the Best average.
3) Add to each column (In order) largest
4) when all have first run add smallest to largest but not if largest is greater or equal to Best average.

I'm unsure if this is the best approach but it is best way I can visualise the process. Turning it into code is another issue.

Hi, Sorry for the delay in writting this up.
I have worked out a solution from the input here & thought it good to pass it on where I got to (If someone has a simular issue it may come in handy)

Steps:-
1) Sort coins with larger first.
2) Add one coin to each pot (From larger to Smaller) i.e. only one coin per pot at this stage.
3) Put the largest coin in the smallest pot till all coins have gone.

This worked for me & I hope it works for others.

Posted 28-Dec-23 3:09am

Knight school

Updated 17-Jan-24 8:37am

v9

Add a Solution

Comments

Richard MacCutchan 28-Dec-23 9:16am

The first thing I would do is to sort the numbers into ascending order. It is then a few simle calculations to find the lowest or highest set. But it is not exactly clear what actual result you are trying to find.

Knight school 28-Dec-23 10:01am

Hi,
Thanks for the reply, As I said it is difficult to explain. I Have updated the question. Hopefully helps

Richard MacCutchan 28-Dec-23 10:20am

Well I still don't understand what the rules are for moving the numbers, or how many numbers are required (or limited to) in each column. For example, why is one column not just [ 50 ]?

0x01AA 28-Dec-23 10:07am

I think it is necessary you make a (better two) consistent example.
Also please explain among other why Col2 results in 700 (and not what I would assume in 750)

Knight school 28-Dec-23 10:21am

My mistake. Col2 corrected.
I will look at the examples but I'm unsure of the output as it is optermisation (Not realy something I can workout). Thanks again.

0x01AA 28-Dec-23 10:24am

Then also please explain Col4=750 (what I expectto be 550)

Knight school 28-Dec-23 10:50am

Again also me (Typo this time). Updated.
Another way to look at this is you have a bag of coins (differant values) & 4 pots. The output result is to fill in the pots with an ammount of coins (coins can only go in one pot & can't be copied) so that the total coin value in each pot in the lowest value accross the pots. There will in most cases be a variation between pot totals but if this kept to a miniumum.(i.e. on ex.2 varition of 100). If seen on a bar graph the bars should be the lowest average height. Does this help?

0x01AA 28-Dec-23 11:16am

In my words (keep in mind I'm not native English):
Distribute the M coins with individual values into N (e.g. here N = 4) pots in a way that every of the N pots contain nearly the same quantity.

In other words:
a.) We have M coins with individual values. Let us call the sum of them is SM.
b.) We have N pots
c.) The optimal distribution of the M coins into the N pots is when every pot holds SM/N 'coin values'

Correct?

[Edit]
It makes it easier, if you click to 'Reply' on a post, other than to use 'Have a Question or Comment'.

Knight school 28-Dec-23 11:26am

Yes, SM/N is optimal but not always achieveable. but how do we make process to get this to best based on the the values of the coins. Once again thanks.
My thoughts are now looking at targeting the optimal (SM/N) by largest to smallest. I'm still in the dark.

0x01AA 28-Dec-23 11:39am

I need time to think about it. Meanwhile I hope that after clarification of the target, some others here will hook in.

It looks pretty like a optimization request. The brute force solution will be to solve it with a downhill algorithm. But I think it is overkill. As I mentioned I need some time.

And you are very welcome with a question that challenges the brain ;)

0x01AA 28-Dec-23 12:56pm

A brute force solution would be:
You calculate every possible distribution of the M coins into the N bags.
The combination for which Delta= Sqrt(Sum((Bag_i - SM/N)^2)) is minimal wins.
Not nice, but maybe a solution.

Knight school 29-Dec-23 5:35am

Thanks, But how do I use this to tell which coin goes in which pot/Bag?

Knight school 28-Dec-23 11:15am

Adding to this I suppose the goal is to get the diffance between the highest pot value to the lowest pot value to be minimal. My intial thoughts were using the sum of all the coins / the number pot = optimal (Average) & then try to work from that. This is where I struggle to break it down. Sorry but I'm dead in the water with this one.

[no name] 28-Dec-23 12:21pm

You're missing a "step". You "discarded" a bunch of numbers and didn't explain why. You need to come up with a given number of "sets"; then worry about where to put them. (Or make a "proper" example)

Knight school 29-Dec-23 5:34am

Sorry I'm unsure on what part you are refering to "Discarded".

CHill60 29-Dec-23 4:31am

Does this answer your question - https://stackoverflow.com/questions/19197836/algorithm-to-evenly-distribute-values-into-containers[^]

Knight school 29-Dec-23 5:27am

I think so but I can't seem to convert to Vb to best read/understand it.

CHill60 29-Dec-23 6:27am

Don't convert it to VB - it's an algorithm - step through it "physically" to understand it - e.g. build pots in a spreadsheet and cut/paste values into them

Knight school 29-Dec-23 5:34am

I have updated the what I have tried to show where I am (Thanks for all the input).

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Gerry Schmitz · Answer 1 · 2023-12-29T08:19:00

Solution 2

I think what you have is a "multiple" knapsacks problem. (Find a link that works for you if not this one).

Solving a Multiple Knapsacks Problem | OR-Tools | Google for Developers[^]

Posted 29-Dec-23 8:19am

Gerry Schmitz