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

[vikrantt]

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?

[scruggsy]

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

[vikrantt]

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.

[scruggsy]

@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?

[vikrantt]

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

[donbock]

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?

[JosAH]

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

[Bassem]

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

[JosAH]

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:

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);
    }
}

If you change the recursive call to this:

                partition(p, n-k, Math.min(n-k, k), i+1);
 

... you get the combinations of all the partitions.

kind regards,

Jos

[scalpa98]

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

[JosAH]

@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:

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

[vedantsharma]

@josah
can this be done iteratively?
without recursion?

[JosAH]

@vedantsharma
Sure, but you need more code; why would you want that?

kind regards,

Jos

[scalpa98]

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);
}
}

[JosAH]

@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

[scalpa98]

Thanks a lot, i will follow your advise.
pascal