Urgent !! please enter

[husseinmd]

hey guys ,
I am supposed to write a recursive function which find the partition of a number n ,, for example if n=3 , it should print 1 1 1 , 1 2 , 3
I wrote the program but i am getting the two partition 1 2 and 2 1 which are the same ,, how can i avoid that ?
this is the code :

void PrintPartition( int n , int A[] , int j  )
{
	if( n<=0 ) {
		printArray( A, j );
		return ;
	}
	for( int i=1 ; i<=n ; i++ )
	{
		A[j]=i;
		PrintPartition( n-i , A ,j+1 ); 
	}
}

the first call of the function is : PrintPartition( n , A , 0 ) ;

Please help mee I have a quiz after 3 hours ..
Thanks in advance :)

[keskiverto]

You start from 1. You should not.
What you actually have to generate for, say n=4, are:
4
3 1
2 2
2 1 1
1 1 1 1

In that representation A[j] >= A[j+1] remains true.


Edit: Well, you can start from 1, but you cannot add numbers that are larger than A[j-1].

[husseinmd]

mmmm could you please tell me how the for loop should look like ?
I got your point but I didn't get how should I write it ..
thanks in advance

[JLBorges]

This is one (more or less de facto standard) way of writing the loop:

#include <iostream>

void print( unsigned int n, const unsigned int A[] )
{
    for( unsigned int i = 0 ; i <= n ; ++i ) std::cout << A[i] << ' ' ;
    std::cout << '\n' ;
}

void print_partitions( unsigned int n, unsigned int A[], unsigned int j = 0 )
{
    if( n > 0 )
    {
        A[j] = n ;
        print( j, A ) ;
        for( unsigned int i = j ? A[j-1] : 1 ; i <= n/2 ; ++i )
        {
            A[j] = i ;
            print_partitions( n-i, A, j+1 ) ;
        }
    }
}

int main()
{
    constexpr unsigned int N = 6 ;
    unsigned int A[N] ;
    print_partitions( N, A );
}

http://ideone.com/zzA4mo