You can read about it in the Scientific American, it´s by Brian Hayes.
If we have a big number of numbers how to divide them so that the two groups are equal ?
It seems that the algorithm for this has not been found yet.
My suggestion:
Make a sum of all numbers, divide in half.
If the number is straight then good, if not then it´s not too bad.
Let´s call this number the aim number.
Then add the first two numbers and try to find if any of the remaining numbers fills the gap between this preliminary sum and the aim number.
If not, add one more and see again.
It´s not perfect yet, but what do you think ?
It´s better than the greedy algorithm, isn´t it ?
5, 24, 598, 6, 29, 30
Sum: 692
half: 346
5 + 24 = 26
gap between 26 and 346 = 320
but 598 is sticking out as too big
An extra algorithm should find out that there is no solution because one number is bigger than the half of all of them.
The easiest hard problem (partition)
-
- Posts: 5621
- Joined: Sun Aug 31, 2014 7:39 am
Re: The easiest hard problem (partition)
Some points:
It would be good if you can provide a link to that article.
You have to be more specific. When you say to divide up the list of numbers so that the groups are equal, equal in what way? Also 5 + 24 = 29, not 26.
PhilX
It would be good if you can provide a link to that article.
You have to be more specific. When you say to divide up the list of numbers so that the groups are equal, equal in what way? Also 5 + 24 = 29, not 26.
PhilX
Re: The easiest hard problem (partition)
I don´t know how to provide a link but if you google "the easiest hard problem Scientific American" you will get it. It worked for me yesterday.
Even without reading the article I put everything in a nutshell for you.
You are right about 24 plus 5. But the idea is still clear I hope.
We did partition when we were young: two strongest bullies picked their teams by taking the best players first, one by one. That´s the greedy algorithm: it takes the largest numbers first, the both sets taking turns.
Equal in number if you add the numbers in both sets.
Example: there is a whole lot of assets differing in value, how to distribute them among two parties equally ?
Even without reading the article I put everything in a nutshell for you.
You are right about 24 plus 5. But the idea is still clear I hope.
We did partition when we were young: two strongest bullies picked their teams by taking the best players first, one by one. That´s the greedy algorithm: it takes the largest numbers first, the both sets taking turns.
Equal in number if you add the numbers in both sets.
Example: there is a whole lot of assets differing in value, how to distribute them among two parties equally ?
-
- Posts: 5621
- Joined: Sun Aug 31, 2014 7:39 am
Re: The easiest hard problem (partition)
Have you ever tried to work this out by computer? Not hard to understand, but could be tedious.duszek wrote:I don´t know how to provide a link but if you google "the easiest hard problem Scientific American" you will get it. It worked for me yesterday.
Even without reading the article I put everything in a nutshell for you.
You are right about 24 plus 5. But the idea is still clear I hope.
We did partition when we were young: two strongest bullies picked their teams by taking the best players first, one by one. That´s the greedy algorithm: it takes the largest numbers first, the both sets taking turns.
Equal in number if you add the numbers in both sets.
Example: there is a whole lot of assets differing in value, how to distribute them among two parties equally ?
PhilX
Re: The easiest hard problem (partition)
In number or total values?
Re: The easiest hard problem (partition)
Total values, yes, that must be the correct term, thank you.
So on one side we can have
25, 125, 50
and on the other 195 and 5.
The problem seems to be that a computer program needs to try all combinations and that means that the number of tries rises exponentially. So a computer is stuck for an eternity.
I would start by calculating the half of the total value of all integers and then I would check if any integer is higher than this.
So on one side we can have
25, 125, 50
and on the other 195 and 5.
The problem seems to be that a computer program needs to try all combinations and that means that the number of tries rises exponentially. So a computer is stuck for an eternity.
I would start by calculating the half of the total value of all integers and then I would check if any integer is higher than this.