in reply to partition of an array
On the matter of dividing up items so that the difference in sum is minimized, you might be interested in this thread Average Price Algorithm. It discusses averages rather than sums and allows for an arbitrary number of buckets, instead of just 2. However, some of the issues will be the same since an average is just a sum divided by the number of elements. There were several suggestions on that thread ranging choosing the best from a random selection of solutions to various techniques for using deviation from the mean. Using deviations from the mean lets one take advantage of the fact that anything that pushes bucket's sum up so that its average is above the average for all elements, must, if possible, be complemented by something below the average for all elements. If you read through the thread discussing that solution and study the counter examples, you will see that its success is sensitive to relative factorizations, but that issue should be easily resolvable for the special case of two buckets.
On the matter of dividing the number of elements into two groups as evenly as possible, you will have to take into account that odd numbers can't be divided evenly by two. There are two ways to deal with this in Perl: one using integers and one using floating point:
Option 1: use floating point division and strip away fractional portion using int:
# scalar returns the number of elements in an array my $n = scalar(@aSomeNumbers); my $n1=int($n/2); my $n2=$n-$n1;
Option 2: Use the mod operator % (see perlop) to determine whether the size of the array is odd or even. $n%2 returns the remainder of division by 2.
# $n%2 will be 1 if $n is odd and 0 if $n is even. my $n=scalar(@aSomeNumbers); my ($n1, $n2); if ($n%2) { #if $n is even it is safe to divide by 2 $n1=$n2=$n/2; } else { #add one so we get an even number again and can divide safely by 2 $n1=($n+1)/2; $n2=$n-$n1; }
Best, beth
|
|---|