Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Ed Wall
Posts:
36
Registered:
12/3/04


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


> 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=sum2s; 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=sum1s; sum2=sum2+s; if (bestj==0) { if (besti!=0) { set2[max2++]=set1[besti]; for (k=besti+1;k<max1;k++) set1[k1]=set1[k]; max1; } } else { temp=set2[bestj]; set2[bestj]=set1[besti]; set1[besti]=temp; tmin=tmins; } return(tmin); }



