Check all combinations of numbers for a given sum

[Killer42]

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.

[JosAH]

Ok I'll bite; just a bit of resursion will do; here's a solution:

[code=java]
import java.util.Array List;
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<I nteger> solution) {

System.out.prin tln(solution);
}

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

if (sum == 0)
solution(soluti on);
else
for (; i < numbers.length && sumsum[i] >= sum; i++) {
if (numbers[i] <= sum) {
solution.add(0, numbers[i]);
solve(numbers, i+1, sum-numbers[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<Integ er>());
}
}[/code]

The numbers that make up the problem need to be in descending order (see the code).

kind regards,

Jos

[r035198x]

Cute integer partitioning that.

[JosAH]

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

[Killer42]

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.

[r035198x]

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.

[Killer42]

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.

[JosAH]

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:

[code=java]
import java.io.IOExcep tion;

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.prin t(solution[i]+" ");
System.out.prin tln();
}

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, sum-numbers[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);
}
}[/code]

kind regards,

Jos

[Killer42]

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
[CODE=vb]
solution(ptr) = numbers(x)
ptr = ptr + 1[/CODE]Correct? And if the "ptr++" had been "++ptr" then the increment would have to be done before the assignment?

[JosAH]

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
[CODE=vb]
solution(ptr) = numbers(x)
ptr = ptr + 1[/CODE]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

[Killer42]

...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.