CODEWITHSUNDEEP
c++recursionpermutation
HG319
HG319

Reputation: 33

Recursion function -counting permuation and ignoring permutation

I am given this problem:

We are going over recursion in my class and I do not quite understand it, I was wondering if someone can help me with this problem

let c(n) be the number of different group integers that can be chosen from the integers 1 through n-1, so that the integers in each group add up to n (for example, n=4=[1+1+1+1]=[1+1+2]=[2+2]). Write a recursive definition for c(n) under the following variations:

a) You count permutations. For example, 1,2,1 and 1,1,2 are two groups that each add up to 4

b)you ignore permutations

I know permutations is how many ways you can arrange a set of numbers, so is my code below correct? I get an answer of 7? Here is my code for part a:

int recurse (int n);

int main(){
    int a=4;
    int sum_perm;
    sum_perm=recurse(a);
    cout<<sum_perm-1<<endl; 
    //Can I do -1 here because it should be from a group of integers from 1 to n-1?  
return 0;
}

int recurse(int n)
{
    int sum = 1;
    if (n == 1){
        return 1;
  }
      for(int i = 1; i < n; i++){
              sum += recurse(n - i); 

   }       
return sum;
}

For part B, if I am not counting permutations, what am I counting? Here is my code for part b:

int without (int n, int max);

int main(){
    int a=4, b =3;
    int sum_without;
    sum_without=without(a,b);
    cout<<sum_without<<endl;

system("Pause");
return 0;
}

int without(int n, int max)

{
    if(n == 1 || max == 1){
        return 1;
}               
    else if (n == max){
        return 1 + without(n, n-1);
        }
    else{
        return without(n,max-1) + without(n-max, max);
        }
}

Upvotes: 2

Views: 1246

Answers (2)

rcgldr
rcgldr

Reputation: 28828

You don't show any code to generate the combinations of numbers that produce a sum. Link to wiki article about partitions .

In this case, the goal is to count the number of combinations and/or permutations, which might be possible without actually generating a set of combinations. Not sure if recursion helps here, but you can convert any loop into recursion if you pass enough variables.

Example "partitions"

1 combination that sums to 1:

1

2 combinations that sum to 2:

1 1
2

3 combinations that sum to 3:

1 1 1
1 2
3

5 combinations that sum to 4:

1 1 1 1
1 1 2
1 3
2 2
4

7 combinations that sum to 5: 

1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
5

11 combinations of numbers that sum to 6:

1 1 1 1 1 1
1 1 1 1 2
1 1 1 3
1 1 2 2
1 1 4
1 2 3
2 2 2
1 5
2 4
3 3
6

Upvotes: 1

Guvante
Guvante

Reputation: 19203

I would recommend combinations directly being considered. While it seems like the more difficult case a simple rule makes it trivial.

Numbers calculated are in decreasing order

This requires you to track the last number, but ensures you don't calculate 1 5 and then 5 1, as the former is impossible.

Upvotes: 0

Related Questions