yeasir007: Java

Algorithm C++ combination Implement without STL Java permutation yeasir007 2018-02-02T18:14:00+06:00

Permutation and Combination

Permutation combination re-arranges members of a set and selects a subset. Go to MATH IS FUN to learn details about permutation and comb...

Read article

Permutation combination re-arranges members of a set and selects a subset. Go to MATH IS FUN to learn details about permutation and combinations.

Here is the implementation of permutation and combination by using recursion function and without using STL.

Permutation:

Here we have used a inputArray having value 5,3,4,2,1. We can replace this input according to our program need.

#include<iostream>
#include<stdio.h>

using namespace std;

int input[5]= {5,3,4,2,1};
int output[25],visited[5];

void permutation(int level,int takenElement,int totalArrayElement);
void printPermutaion(int takenElement);

int main()
{
    for(int t=0;t<5;t++)
    {
        permutation(0,t,5);
    }
    return 0;
}

void permutation(int level,int takenElement,int totalArrayElement)
{
    if(level == takenElement)
    {
        printPermutaion(takenElement);
        return;
    }

    for(int i=0;i<totalArrayElement;i++)
    {
        if(!visited[i])
        {
            visited[i] = true;
            output[level] = input[i];
            permutation(level+1,takenElement,totalArrayElement);
            visited[i] = false;
        }
    }
}

void printPermutaion(int takenElement)
{
    for(int i=0;i<takenElement;i++)
    {
        cout << output[i] << " " ;
    }

    cout << endl;
}

Algorithm C++ Implement without STL Java Recursion 2018-01-30T12:34:00+06:00

Recursion

What is recursion? Sometimes a problem is too difficult or too complex to solve because it is too big. If the problem can be broken do...

Read article

What is recursion?

Sometimes a problem is too difficult or too complex to solve because it is too big. If the problem can be broken down into smaller versions of itself, we may be able to find a way to solve one of these smaller versions and then be able to build up to a solution to the entire problem. This is the idea behind recursion; recursive algorithms break down a problem into smaller pieces which you either already know the answer to, or can solve by applying the same algorithm to each piece, and then combining the results.

Identify the 3 parts of the recursive algorithm :

All recursive algorithm must have the following three stages:

Base Case: if ( actualResult() == 2 ) result = a + b;
"Work toward base case": a+b becomes the first parameter
This reduces the number of parameters to the function from 3 to 2, and 2 is the base case!
Recursive Call: add_numbers(a+b, c);

Why recursion works?

In a recursive algorithm, the computer "remembers" every previous state of the problem. This information is "held" by the computer on the "activation stack" (i.e., inside of each functions workspace).
Every function has its own workspace PER CALL of the function.

As an example we will discuss about computing Factorial of a number. What is the factorial of number X?
*** factorial(X) = X * (x-1) * (x-2) * ... * 2
But "(x-1) * (x-2) * ... * 2" is the equal of factorial(X-1)
So combine definition would be factorial(X) = X * factorial(X-1);

[Problem]
Find the factorial value of the given number, X (1 <= x <= 20) and print as shown below:
The given number is greater than or equal to 1 and less than or equal to 20.

[Input]
The first input line contains the number of test cases, T.
Then, T number of input will be given.

[Output]
For each given test case, print the factorial value.

INPUT =============
3 // number of Test cases
9 // Test case index
12 20

OUTPUT
===============================
#1 9! = 362880
#2 12! = 479001600

#3 20! = 2432902008176640000

Solution for C++:

#include
using namespace std;

long long factorial(int num);

int main(void)
{
    int test_case;
    int T;
    int num;
    long long value;

    freopen("CreateRecursion.txt", "r", stdin);
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        scanf("%d", &num);
        value = factorial(num);
        printf("#%d %d! = %lld\n", test_case, num, value);
    }
}

long long factorial(int num)
{
    if (num == 0)
    {
        return 1;
    }
    else
    {
        return num * factorial(num - 1);
    }
}

Solution for Java: