Math Forum Discussions

Ed Wall

Posts: 36
Registered: 12/3/04

Re: Errors, Approximations and Combinatorics
Posted: Feb 22, 1996 11:41 PM

Plain Text

> Rex said,
>
> I have proposed to him that I will give him 200 numbers (say 5 or 6
> digit numbers). His job is to put the numbers into 2 sets such that
> the sums of the numbers in the two sets are equal (or a close as
> possible). Is there an algorithm that will allow Shane to do this, or
> is the only method brute force? If the latter, I reckon Shane's
> Pentium could have more than 200C100 loops to run through, which is a
> very big number.
>
>
> I've been thinking about this problem in my "down time" all day and I
> think I have a fairly easy solution. Please tell me if I am being
> naive or stupid.
>
> First let me qualify this by saying I am not a programmer and I have
> no idea how to get a computer to do this, but as a human, how about if
> I just start listing the numbers in two groups, trying to keep the
> running sum about equal, until I get all the numbers listed. Let's
> say when I get done group 1 has a sum that is 1238 more than group 2.
> Can't I then start on a new task of finding two numbers (one from each
> group) which differ by 619? If I switch those two the result will be
> two equal stacks. If I can't find two such numbers, I should at least
> be able to narrow the gap. I see that this might take a while and
> that I won't always be able to find numbers to narrow the gap, but I
> could at least keep it reasonable until I get a gap that can be fixed
> exactly. Yes this is inefficient, but is there a quicker way? And
> how about it hackers, can we write a program to do this?
>
> Sam Evers
> University of Alabama

Here is a hack in C. I could have done it in some other language, but I'm a bit
rusty in C right now. Note I make a simplification that one pile can essentially
be held larger and you need to introduce a zero number to one switch - sort of
like zen :-)

Some speed improvements would be to sort each pile so you could break out of
comparisons when obvious.

I think I understood Sam's logic and it seems that one could even show that
this thing might converge.

#include <stdio.h>

#define N 26

int n[N+1];
int sum1, sum2, max1, max2;
int set1[N+1], set2[N+1];

void main()
{
int i, j, s, min, tmin, newtmin;
int sitcheroo();

/* Set your numbers here. A kludge because I'm lazy. BTW these are the */
/* first 26 primes and if you put one in the set then you can get equal */
/* partitions */

n[1]=97; n[2]=89; n[3]=83; n[4]=79; n[5]=73; n[6]=71;
n[7]=67; n[8]=67; n[9]=61; n[10]=59; n[11]=53; n[12]=47;
n[13]=43; n[14]=41; n[15]=37; n[16]=31; n[17]=29; n[18]=23;
n[19]=19; n[20]=17; n[21]=13; n[22]=11; n[23]=7; n[24]=5;
n[25]=3; n[26]=2;

/* Assume n[1] is the largest number to be considered */

clrscr();
n[0]=0;
sum1=n[1];
sum2=0;
set1[0]=0;
set1[1]=1;
set2[0]=0;
max1=2;
max2=1;

for (i=2;i<=N;i++) {
if (sum2 < sum1) {
sum2 = sum2 +n[i];
set2[max2++] = i;
}
else {
sum1 = sum1 + n[i];
set1[max1++] = i;
}
}

if (sum1 <sum2) {
s=n[set2[--max2]];
sum1=sum1+s;
sum2=sum2-s;
set1[max1++]=set2[max2];
}

/* Thus we can assume sum1 >= sum2 */
min = sum1 - sum2;
if (min!=0) {
tmin = min/2;
newtmin=tmin+1;

while (newtmin>tmin) {
newtmin=tmin;
tmin=switcheroo(tmin);
}
}
printf("First Set %d\n",sum1);
for (i=1;i<max1;i++) printf("%d\n",n[set1[i]]);
printf("\n\nSecond Set %d\n",sum2);
for (i=1;i<max2;i++) printf("%d\n",n[set2[i]]);
}

int switcheroo(tmin)
int tmin;
{
int i, j, k, s, smax, temp;
int besti, bestj;

smax=0;
besti=0;
bestj=0;
for (i=1;i<max1;i++) {
for (j=0;j<max2;j++) {
s=n[set1[i]]-n[set2[j]];
if (s>0) {
if (s<=tmin) {
if (s>smax) {
besti=i;
bestj=j;
smax=s;
}
}
}
}
}
s=n[set1[besti]]-n[set2[bestj]];
sum1=sum1-s;
sum2=sum2+s;
if (bestj==0) {
if (besti!=0) {
set2[max2++]=set1[besti];
for (k=besti+1;k<max1;k++) set1[k-1]=set1[k];
max1--;
}
}
else {
temp=set2[bestj];
set2[bestj]=set1[besti];
set1[besti]=temp;
tmin=tmin-s;
}
return(tmin);
}