Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/forums/cpp/)
-   -   Recursion and Permutations (http://www.go4expert.com/forums/recursion-and-permutations-t19263/)

neox08 2Sep2009 01:14

Recursion and Permutations
 
Hi, I need some serious help with permutations and recursion. I understand how both work together, but I need some help with the following.

Basically the main function asks for a user entered number, and the recursion function takes that number and sees how many combinations of sums add up to that number. It then returns that number, which is count in my program below, and prints it out. I have it working to print all the numbers including permutations such as:

user entered number = 3 so with permutations (1,2) = 3, (2,1) = 3, (1,1,1) = 3. So the returned count would be 3.

What I also need the program to do is, without taking out the permutations, have it also find without permutations and return that number as well as with permutations. For example:

user entered number = 3 so without permutations (1,2) = 3, (1,1,1) = 3. So the returned count would be 2.

I must be able to do all this within a single function called recursion and output both permutations and without permutations in the main function.

Here is the working code I have for 'with permutations':

Code:

#include <iostream>
using namespace std;

/**Recursive function which checks the of numbers (permutations included) to
 * count how many choices of sums add to the user-entered number.
 * @param n An int type user-entered number from the main function
 * @pre The main function prompts the user for an integer and stores it as number.
 *      The function recursion takes that input and finds all possible sums, including
 *      permutations. The recursion function has two base cases that return set answers,
 *      and the rest is calculated through recursion by putting k into the function
 *      call. It goes through the for loop and counts each one while using the count+=
 *      to keep track of the count.
 * @post After the pre-condition, it returns the number of sums that add up to the user
 *      inputed number, which is equal to count. The main function then prints out
 *      the returned number equal to count in the recursion function.
 */

int recursion(int n) //Recursion Function
{
  int count = 0; // Counter with Permutations
  int count2 = 0; // Counter without Permutations

  if(n == 1)  //Base Case:1
  { 
      return 0;
  }  // end if

  if(n == 2)  //Base Case:2
  { 
      return 1;
  }  // end if

    for(int k = 1; k < n; k++)
    { 
      int x = n-k;
      count++;
      count+= recursion(k); //Recursive Call
    }  // end for       

    return count;
}  // end recursion

int main()  //Used to get user-input and call recursion function
{
  int number; //User-entered number

  cout << "Please choose a number: ";
  cin >> number;

  int returnedValue = recursion(number); // Function Call to recursion

  cout << "There are " << returnedValue << " possible sums." << endl; //Display Number

}  // end main

Thanks in advance for your help! :happy:

xpi0t0s 2Sep2009 12:12

Re: Recursion and Permutations
 
Try starting the k loop at n instead of 1.


All times are GMT +5.5. The time now is 20:34.