By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
 429,313 Members | 2,798 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 429,313 IT Pros & Developers. It's quick & easy.

# Print all combinations of a number N, as a sum of positive integers?

 P: 7 For example: 3= 2 1 1 2 1 1 1 4= 3 1 1 3 1 1 2 1 2 1 2 1 1 1 1 1 1 and so on... How to write a program in C for such a problem...I can't even seem to figure out the algo? May 18 '09 #1
Share this Question
15 Replies

 100+ P: 147 @vikrantt Some thoughts: -for every number c less than n, c + (n - c) = n -given the above, you can do this recursively. For instance, if 2 + 3 = 5 then the numbers summing to 2 plus the numbers summing to 3 also = 5. -you only have to calculate sums for numbers from (n/2) through n; below that the sums are the same, just reversed. i.e. 4 + 2 = 6 3 + 3 = 6 2 + 4 = 6 <- you can stop at 3 + 3 Hope this helps. May 18 '09 #2

 P: 7 okay, i think i did not make it clear. But I do not need to calculate the numbers, rather print them. And here 1 2, is different than 2 1. Or may be we can skip permutation. May 18 '09 #3

 100+ P: 147 @vikrantt I'm not clear on what you need, then. Do you already have an algorithm to compute the numbers, or are the numbers precomputed? That would be the first step before you can worry about printing them. If you've already got the first step down, are you stuck on how to output the numbers to the screen? May 18 '09 #4

 P: 7 no....u do not need to count the numbers...i mean its not that u must not...but only thing required is to print them.... counting is not really a concern here.... May 18 '09 #5

 Expert 100+ P: 2,398 I hear you telling us that you already have a solution for the much harder problem of determining the "additive factors" of a number N and that you only need help printing out that list of numbers after you have generated the list. Is that what you mean? May 18 '09 #6

 Expert 10K+ P: 11,448 You mention combinations in your thread title but you mention permutations of an integer number in your post. Maybe you are interested in this link. kind regards, Jos May 18 '09 #7

 100+ P: 344 @JosAH Wow I was going to suggest a simple algorithm to do that, but you surprised me a lot. Also I think you (all) didn't agree on the definition of counting, he wants to calculate the numbers then printing them out the screen. May 23 '09 #8

 Expert 10K+ P: 11,448 I coughed up a bit of Java code (sorry, no C/C++ compiler on this laptop, I'm sitting outside in my garden and am way too lazy to move in to find one of my other laptops). The following code snippet does what the OP wants: Expand|Select|Wrap|Line Numbers public class Partition {       private static void printPartition(int[] p, int n) {           for (int i= 0; i < n; i++)             System.out.print(p[i]+" ");         System.out.println();     }       private static void partition(int[] p, int n, int m, int i) {           if (n == 0)             printPartition(p, i);         else             for (int k= m; k > 0; k--) {                 p[i]= k;                 partition(p, n-k, n-k, i+1);             }     }       public static void main(String[] args) {           partition(new int, 6, 6, 0);     } } If you change the recursive call to this: Expand|Select|Wrap|Line Numbers                 partition(p, n-k, Math.min(n-k, k), i+1);   ... you get the combinations of all the partitions. kind regards, Jos May 23 '09 #9

 P: 3 hello i am a teacher in a primary school who try to program in vb as hobbyist. (i com here by googling ) I am interested in a code in vbnet or C# able to find all the partition in 2 or 4 terms of any numbers n. Is you java code able to do that ? If yes, Do you know how to translate it in C# or VB please? thank you pascal I would like to build a software for my young pupils : here is the goal Tables of numbers: In a table of numbers, pupils have to find the pairs (vertical or horizontal numbers side by side) whose sum is 10 (for example). or a variant that is finding squares with the numbers (quadruplets?) gives 100 (for example in yellow in the grid). Objectives: To bring the children to make many calculations to track down peers or square in question. I want to automate the creation of job as upper. However, mathematically speaking, I wonder if there is an "equation" that would find all the pairs or quadruplets of a number? The user variables to integrate are: the size of the grid: LgGrille and HtGrille as integer the target number: NbCible as integer (or decimal?) The type of work (pairs / quadruplets) JobType The amount of peers / quadruplets hidden in the grid: QteJob The allowed or prohibited overlay solutions possible (as boolean?) The table of possible pairs or quadruplets calculated and stored as array? ArrayPatterns Pseudo code: 1. Find all the possible patterns and store them in an array? Calculate the number of possible Patterns: Nbpatterns 2. Show this number in the user interface to choose an intelligent QteJob (If QteJob> Nbpatterns, then it will use several times the same ArrayPatterns.item) 3. Place the QteJob ArrayPatterns.items randomly on the grid within the non-overlapping, if it is prohibited 4. Finish filling the grid with numbers being careful not to accidentally create new ArrayPatterns.item 5. Using the same way to print the job as Maze and magic square May 24 '09 #10

 Expert 10K+ P: 11,448 @scalpa98 Sure, my code can do that: in the printPartition() method bail out if the length n of the partition doesn't equal the wanted length, so insert at line #4: Expand|Select|Wrap|Line Numbers if (n != WANTED_LENGTH) return; // bail out   The rest of your problem description suggests another solution to your (badly defined) problem though. Start your own thread because this is a completely different problem. kind regards, Jos May 25 '09 #11

 P: 2 @josah can this be done iteratively? without recursion? May 26 '09 #12

 Expert 10K+ P: 11,448 @vedantsharma Sure, but you need more code; why would you want that? kind regards, Jos May 26 '09 #13

 P: 3 Hello again and thanks for your reply Jos. I would like to store all the possible partition of a number in four terms in an array. In fact , i just wanted to know if a vb version of this code exists in vbnet (it's the language i know a little) Or is it possible to translate it in vb with a tool? thanks public class Partition { private static void printPartition(int[] p, int n) { for (int i= 0; i < n; i++) System.out.print(p[i]+" "); System.out.println(); } private static void partition(int[] p, int n, int m, int i) { if (n == 0) printPartition(p, i); else for (int k= m; k > 0; k--) { p[i]= k; partition(p, n-k, n-k, i+1); } } public static void main(String[] args) { partition(new int, 6, 6, 0); } } May 26 '09 #14

 Expert 10K+ P: 11,448 @scalpa98 Storing all (size 4) partitions in an array is easy too: everytime the printPartition() method is called, check n (if it isn't equal to 4 bail out) and store the current partition somewhere. I don't know any Visual Basic; you can take my code over to the Visual Basic forum and ask if some kind sould wants to translate it for you. I don't know of any Visual Basic translators that translate another language (like Java) to Visual Basic. kind regards, Jos May 27 '09 #15

 P: 3 Thanks a lot, i will follow your advise. pascal May 27 '09 #16

### Post your reply

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