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
Bytes IT Community
+ 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
Share on Google+
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
  1. public class Partition {
  2.  
  3.     private static void printPartition(int[] p, int n) {
  4.  
  5.         for (int i= 0; i < n; i++)
  6.             System.out.print(p[i]+" ");
  7.         System.out.println();
  8.     }
  9.  
  10.     private static void partition(int[] p, int n, int m, int i) {
  11.  
  12.         if (n == 0)
  13.             printPartition(p, i);
  14.         else
  15.             for (int k= m; k > 0; k--) {
  16.                 p[i]= k;
  17.                 partition(p, n-k, n-k, i+1);
  18.             }
  19.     }
  20.  
  21.     public static void main(String[] args) {
  22.  
  23.         partition(new int[6], 6, 6, 0);
  24.     }
  25. }
If you change the recursive call to this:

Expand|Select|Wrap|Line Numbers
  1.                 partition(p, n-k, Math.min(n-k, k), i+1);
  2.  
... 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
  1. if (n != WANTED_LENGTH) return; // bail out
  2.  
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, 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.