469,344 Members | 6,185 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,344 developers. It's quick & easy.

Check all combinations of numbers for a given sum

8,435 Expert 8TB
We have received what looks to me like quite an interesting question in the Visual Basic forum concerning how to check all possible combinations of numbers in a list for those where the sum matches a given number. (That's if I'm explaining it correctly.)

Any mathematicians care to have a look?

If we can come up with an algorithm I expect translating it to VB will be easy enough.
Mar 11 '08 #1
10 10428
JosAH
11,448 Expert 8TB
Ok I'll bite; just a bit of resursion will do; here's a solution:

Expand|Select|Wrap|Line Numbers
  1. import java.util.ArrayList;
  2. import java.util.List;
  3.  
  4. public class Sum {
  5.     private static int[] numbers= { 6, 5, 4, 3, 2, 1 };
  6.     private static int[] sumsum= new int[numbers.length];
  7.  
  8.     private static int sum= 10;
  9.  
  10.     private static void solution(List<Integer> solution) {
  11.  
  12.         System.out.println(solution);
  13.     }
  14.  
  15.     private static void solve(int[] numbers, int i, int sum, List<Integer> solution) {
  16.  
  17.         if (sum == 0) 
  18.             solution(solution);
  19.         else
  20.             for (; i < numbers.length && sumsum[i] >= sum; i++) {
  21.                 if (numbers[i] <= sum) {
  22.                     solution.add(0, numbers[i]);
  23.                     solve(numbers, i+1, sum-numbers[i], solution);
  24.                     solution.remove(0);
  25.                 }
  26.             }
  27.     }
  28.  
  29.     public static void main(String[] args) {
  30.  
  31.         for (int s= 0, i= numbers.length; --i >= 0; ) {
  32.             sumsum[i]= numbers[i]+s;
  33.             s+= numbers[i];
  34.         }
  35.         solve(numbers, 0, sum, new ArrayList<Integer>());
  36.     }
  37. }
The numbers that make up the problem need to be in descending order (see the code).

kind regards,

Jos
Mar 14 '08 #2
r035198x
13,262 8TB
Cute integer partitioning that.
Mar 14 '08 #3
JosAH
11,448 Expert 8TB
Cute integer partitioning that.
Yep, but I guess the answer isn't as interesting as the question was; no replies
nor any interest from the Basic droids; oh well ... ;-)

kind regards,

Jos
Mar 18 '08 #4
Killer42
8,435 Expert 8TB
Yep, but I guess the answer isn't as interesting as the question was; no replies
nor any interest from the Basic droids; oh well ... ;-)
Probably because the solution is written in gibberish.

Oh, sorry. They call that "Java" these days. ;)

Guess we'll have to mount a translation project.
Mar 18 '08 #5
r035198x
13,262 8TB
Probably because the solution is written in gibberish.

Oh, sorry. They call that "Java" these days. ;)

Guess we'll have to mount a translation project.
I can translate that to C# if you want ... not that it will look much different but it's the only .NET language I can write code in without feeling ashamed of myself.
Just look at it as pseudo code and pick up the recursion used for the generating function.
Mar 19 '08 #6
Killer42
8,435 Expert 8TB
I can translate that to C# if you want ... not that it will look much different but it's the only .NET language I can write code in without feeling ashamed of myself.
Just look at it as pseudo code and pick up the recursion used for the generating function.
Yeah, I think the overall structure with the recursion is simple enough to understand. It's the specifics of what certain statements or references mean that stopped me when I glanced over it. Will have a proper look over the long weekend and see if it makes any more sense.
Mar 20 '08 #7
JosAH
11,448 Expert 8TB
Yeah, I think the overall structure with the recursion is simple enough to understand. It's the specifics of what certain statements or references mean that stopped me when I glanced over it. Will have a proper look over the long weekend and see if it makes any more sense.
I'll make it easier for you and mutilate the previous algorithm implementation:

Expand|Select|Wrap|Line Numbers
  1. import java.io.IOException;
  2.  
  3. public class Sum {
  4.     private static int[] numbers= { 6, 5, 4, 3, 2, 1 };
  5.     private static int[] solution= new int[numbers.length];
  6.     private static int ptr= 0;
  7.     private static int[] sumsum= new int[numbers.length];
  8.  
  9.     private static int sum= 10;
  10.  
  11.     private static void solution() {
  12.  
  13.         for (int i= 0; i < ptr; i++)
  14.             System.out.print(solution[i]+" ");
  15.         System.out.println();
  16.     }
  17.  
  18.     private static void solve(int[] numbers, int i, int sum) {
  19.  
  20.         if (sum == 0)
  21.             solution();
  22.         else
  23.             for (; i < numbers.length && sumsum[i] >= sum; i++) {
  24.                 if (numbers[i] <= sum) {
  25.                     solution[ptr++]= numbers[i];
  26.                     solve(numbers, i+1, sum-numbers[i]);
  27.                     ptr--;
  28.                 }
  29.             }
  30.     }
  31.  
  32.     public static void main(String[] args) throws IOException {
  33.  
  34.         for (int s= 0, i= numbers.length; --i >= 0; ) {
  35.             sumsum[i]= numbers[i]+s;
  36.             s+= numbers[i];
  37.         }
  38.         solve(numbers, 0, sum);
  39.     }
  40. }
kind regards,

Jos
Mar 20 '08 #8
Killer42
8,435 Expert 8TB
I'll make it easier for you and mutilate the previous algorithm implementation ...
Thanks. Ended up being too busy over the long weekend. Will try to get into it this week.

I really hate the two-in-one features of Java, though. You know, things like... solution[ptr++]= numbers[x]; - I believe this would translate as something like
Expand|Select|Wrap|Line Numbers
  1. solution(ptr) = numbers(x)
  2. ptr = ptr + 1
Correct? And if the "ptr++" had been "++ptr" then the increment would have to be done before the assignment?
Mar 25 '08 #9
JosAH
11,448 Expert 8TB
Thanks. Ended up being too busy over the long weekend. Will try to get into it this week.

I really hate the two-in-one features of Java, though. You know, things like... solution[ptr++]= numbers[x]; - I believe this would translate as something like
Expand|Select|Wrap|Line Numbers
  1. solution(ptr) = numbers(x)
  2. ptr = ptr + 1
Correct? And if the "ptr++" had been "++ptr" then the increment would have to be done before the assignment?
Yep, correct; it isn't a Java invention. In the dark ages CPL already implemented
those pre- and post-increments. BCPL inherited them and later along the path
B, C, C++ and Java implemented those operators as well. The operators are
directly inspired by the 'inc' machine code instructions that were/are available
on many processors and are quite handy when you get used to them.

kind regards,

Jos
Mar 25 '08 #10
Killer42
8,435 Expert 8TB
...quite handy when you get used to them.
Oh yes, I can see how they'd allow much more compact code. It just seems as though it comes at too high a cost in readability.

Perhaps I simply need more experience.
Mar 26 '08 #11

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

reply views Thread by suzy | last post: by
4 posts views Thread by pauljwilliams | last post: by
15 posts views Thread by Thomas Cameron | last post: by
5 posts views Thread by Phil | last post: by
1 post views Thread by arushgadkar | last post: by
5 posts views Thread by Bails | last post: by
2 posts views Thread by zgfareed | last post: by
reply views Thread by suresh191 | last post: by
1 post views Thread by Marylou17 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.