Would I need to form all permutations and combinations for the following?

Question

You have a number of stones with known weights w1, …, wn.

Write a program that will rearrange the stones into two piles such that weight difference between the piles is minimal.

Answer 1

Although this is a one dimensional knastpsack problem, here is another mathematical way of doing this.

Algorithm: 1D Optimization
Input: weights (sequenc of weights)
Output: left and right, two sequences with difference between sum of elements minimized
***************************************************************************************

1) Sort weights in descending order
2) initialize leftsum = 0, rightsum = 0
3) initialize leftseq = [], rightseq = []
4) for each weight in weights repeat
 4.1) if leftsum = 0 then
  4.1.1) leftsum = weight
  4.1.2) leftseq.add(weight)
 4.2) else if rightsum = 0 then
  4.2.1) rightsum = weight
  4.2.2) rightseq.add(weight)
 4.3) else
  4.3.1) error_left = absolute(leftsum - weight)
         error_right = absolute(rightsum - weight)
  4.3.2) if error_left >= error_right then
   4.3.2.1) rightsum = rightsum + weight
   4.3.2.2) rightseq.add(weight)
  4.3.3) else
   4.3.3.1) leftsum = leftsum + weight
   4.3.3.2) leftseq.add(weight)
 

// And here is a sample implementation of the above hypothesis in python

numbers = [1, 23, 100, 857, 890, 78, 54, 789, 34, 47, 900];
#numbers = [1, 23, 16, 5, 2]
print numbers
numbers.sort(reverse=True)
print numbers

leftSum = 0;
rightSum = 0;

leftSeq = [];
rightSeq = [];

for num in numbers:
 if leftSum == 0:
  leftSum = num;
  leftSeq.append(num);
 elif rightSum == 0:
  rightSum = num;
  rightSeq.append(num);
 else:
  errorLeft = abs(leftSum - num);
  errorRight = abs(rightSum - num);
  if errorLeft >= errorRight:
   rightSum += num;
   rightSeq.append(num);
  else:
   leftSum += num;
   leftSeq.append(num);

print leftSum;
print rightSum;
print leftSeq;
print rightSeq;
  

It should work. Your sequences are now in leftseq and rightseq.

Answer 2

No. You needn't create all 2^n combinations. There are two ways for avoiding it.

1. Even if you will create many combinations and compare them, you can use preliminary filtering. While you have made only part of the combination, setting some m (m < n) stones, you can some times check, if you can develop from it a good combination. For example, you can already have too big weight in one of the piles.
2. Maybe you can find some existing algorithm, that will create the needed composition without any combinations. You can invent it yourself or find an already existent one.

Even if you'll find an algorithm, remember, you MUST learn how to create your own algorithm for the sorting with preliminary filtering. For there are many tasks in real life where you will need this skill.