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.
10 10428
Ok I'll bite; just a bit of resursion will do; here's a solution: 
import java.util.ArrayList;

import java.util.List;


public class Sum {

private static int[] numbers= { 6, 5, 4, 3, 2, 1 };

private static int[] sumsum= new int[numbers.length];


private static int sum= 10;


private static void solution(List<Integer> solution) {


System.out.println(solution);

}


private static void solve(int[] numbers, int i, int sum, List<Integer> solution) {


if (sum == 0)

solution(solution);

else

for (; i < numbers.length && sumsum[i] >= sum; i++) {

if (numbers[i] <= sum) {

solution.add(0, numbers[i]);

solve(numbers, i+1, sumnumbers[i], solution);

solution.remove(0);

}

}

}


public static void main(String[] args) {


for (int s= 0, i= numbers.length; i >= 0; ) {

sumsum[i]= numbers[i]+s;

s+= numbers[i];

}

solve(numbers, 0, sum, new ArrayList<Integer>());

}

}
The numbers that make up the problem need to be in descending order (see the code).
kind regards,
Jos
Cute integer partitioning that.
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
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.
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.
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.
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: 
import java.io.IOException;


public class Sum {

private static int[] numbers= { 6, 5, 4, 3, 2, 1 };

private static int[] solution= new int[numbers.length];

private static int ptr= 0;

private static int[] sumsum= new int[numbers.length];


private static int sum= 10;


private static void solution() {


for (int i= 0; i < ptr; i++)

System.out.print(solution[i]+" ");

System.out.println();

}


private static void solve(int[] numbers, int i, int sum) {


if (sum == 0)

solution();

else

for (; i < numbers.length && sumsum[i] >= sum; i++) {

if (numbers[i] <= sum) {

solution[ptr++]= numbers[i];

solve(numbers, i+1, sumnumbers[i]);

ptr;

}

}

}


public static void main(String[] args) throws IOException {


for (int s= 0, i= numbers.length; i >= 0; ) {

sumsum[i]= numbers[i]+s;

s+= numbers[i];

}

solve(numbers, 0, sum);

}

}
kind regards,
Jos
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 twoinone features of Java, though. You know, things like... solution[ptr++]= numbers[x];  I believe this would translate as something like 
solution(ptr) = numbers(x)

ptr = ptr + 1
Correct? And if the "ptr++" had been "++ptr" then the increment would have to be done before the assignment?
Thanks. Ended up being too busy over the long weekend. Will try to get into it this week.
I really hate the twoinone features of Java, though. You know, things like... solution[ptr++]= numbers[x];  I believe this would translate as something like 
solution(ptr) = numbers(x)

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 postincrements. 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
...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.
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 MN 
last post: by

4 posts
views
Thread by pauljwilliams 
last post: by

15 posts
views
Thread by Thomas Cameron 
last post: by

7 posts
views
Thread by zjut 
last post: by

5 posts
views
Thread by Phil 
last post: by
 
5 posts
views
Thread by Bails 
last post: by

2 posts
views
Thread by zgfareed 
last post: by
          