CODEWITHSUNDEEP
c++algorithmrecursion
Aaron B
Aaron B

Reputation: 97

Recursive solution for Permutations

Hey I have a problem where I need to create two functions, countWithPerms() and ignorePerms() These two functions must be a recursive solution. countWithPerms() will count the number of actual permutations while ignorePerms() will only count the number of duplicate permutations.

So an example would be find the permutation for the number 3. So if I pass 3 into the function countWithPerms() would find that 3 = (2 + 1) = (1 + 2) = (1 + 1 + 1), so countWithPerms(3) is 3, because it counted 3 ways to sum up 3. While countIgnorePerms(3) is 2 because (1 + 2) and (2 + 1), would both not be counted in countWithPerms since they are the just written in the opposite order.

A large example would be countWithPerms(7) is 63, while countIgnorePerms(7) is 14.

I have countwithPerms done, but I am completely stuck on countIgnorePerms.

 int countWithPerms( int n)
 {
     if(n == 1)
           return 0;
     else
           n--;
     return (countWithPerms(n) + 1) + 
            (countWithPerms(n));
}

    int ignorePerms(int sum, int xmin){
    if(sum == 1)
           return 0;

        else
        for(int i=0; i<sum;i++){
            sum += sum-xmin;
            2*ignorePerms(sum,xmin)+1;

                 return sum;
    }
}

Upvotes: 2

Views: 164

Answers (1)

6502
6502

Reputation: 114461

The idea of counting without considering permutations is to consider only ordered solutions.

To do this pass in addition to n also what is the minimum value xmin that an addendum must have. For example

3 = 1 + 2

would be ok (because 2 >= 1), but

3 = 2 + 1

wouldn't be acceptable (because 1 < 2).

So the idea is to write a function that answers "how many sums with non-decreasing terms can give the prescribed total in the first addendum is not less than min_addendum?".

  1. if min_addendum is bigger than total clearly the answer is 0
  2. if total is 1 then there's only one sum
  3. otherwise the first possible sum is total, then you should count as sums
    • min_addendum + a sum of other non-decreasing terms, the first not less than min_addendum totalling total-min_addendum
    • min_addendum+1 + a sum of other non-decreasing terms, the first not less than min_addendum+1 totalling total-min_addendum-1
    • min_addendum+2 + a sum of other non-decreasing terms, the first not less than min_addendum+2 totalling total-min_addendum-2
    • ...

Upvotes: 1

Related Questions