473,890 Members | 2,012 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Check all combinations of numbers for a given sum

8,435 Recognized Expert Expert
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 10785
JosAH
11,448 Recognized Expert MVP
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 MVP
Cute integer partitioning that.
Mar 14 '08 #3
JosAH
11,448 Recognized Expert MVP
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 Recognized Expert Expert
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 MVP
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 Recognized Expert Expert
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 Recognized Expert MVP
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 Recognized Expert Expert
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 Recognized Expert MVP
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

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

Similar topics

0
1502
by: suzy | last post by:
Hi, i'm from belgium, europe, and my english is not perfect, so my excuses. I ame looking for someone ho can help me with my problem. I want to compare combinations in an imputfile, and if they have 2 or 3 or more the same numbers i want remove then; all the combinations have to be compared i give you an example: the imput file: 1, 2, 3, 4, 5, 6 1, 2, 3, 4, 8, 9 4, 5, 6, 10, 12, 15
4
1272
by: MN | last post by:
Hello all - I have done ASP for a while but never found a quick way to handle this issue. I have 8 dropdown boxes. Is there an easy to check that only 1 has selected 'Yes' and the others are 'No' without checking infinite combinations? I usually do this with alot of coding for the combinations. Any thoughts are appreciated.
4
5546
by: pauljwilliams | last post by:
Hi there, I'm looking for an algorithm that will generate combinations in the following way: Given a lower bound, and an upper bound, generate a set of size n containing all combinates of numbers between the bounds. e.g if lower_bound = 5, upper bound = 7, size = 3, the algorithm would generate:
15
2428
by: Thomas Cameron | last post by:
Hello all, I have an array of values which I would like to generate all possible combinations for. And example would be the values "a,b,c". This would produce the following: a ab abc ac b
7
13999
by: zjut | last post by:
I need to implement the method : round(String name, int index) The given string maybe the every type of float type, ( the msdn given the regax is that : integral-digits]exponential-digits]) and the index is the location after "." in name. First, i should check the given name is a valid float-point, and then, to check the number in name in index locaion is > 0 or not? eg:
5
8171
by: Phil | last post by:
Thank you for reading my plea for help. What I'm trying to achieve is to get the subsets from a given set using the Standard Template Library. Say, for example, I have created an empty set and then have inserted 3 numbers into that set (1, 2, 3). Next, I would like to get all of the subset pairs (1, 2), (1, 3) and (2, 3) for processing. A Google search has given me a lot to think about but nothing specific for
1
1757
by: arushgadkar | last post by:
Hello , I want a code for generating combinations in C++ /C for example ... say you have numbers from 1,2,3,4,5.....15 . You want all possible combinations of 5 numbers . like (1,2,3,4,5), ( 3 ,10 ,11, 14,16) .... etc Your help will be greatly appreciated. Regards Arush .
5
5971
by: Bails | last post by:
Hi all I have a theory for a lotto system and need help on how to code it. I want to create 1 massive database with EVERY combination of numbers possible in a given lotto system, then remove all the numbers in a sequence. For example, in Australia our lotto system has 45 balls and you need to pick 6 numbers to win the jackpot.
2
2278
by: zgfareed | last post by:
Can anyone suggest an algorithm or function to generate combinations/ permutations of a group of substrings stored in a vector. The substrings consists of 3 letters and the resulting string combinations should be of a size that is a multiple of 3.
0
9810
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
11207
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
1
10896
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
10443
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
5830
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
6031
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4652
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
4251
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3259
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.