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 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;
}

This program will print all possible combination like bellow:

If we want to generate permutation having a specific number we need to modify our main function call. Suppose if we want to generate permutation by taking all number. like "5 2 3 4 1", "1 2 3 4 5", " 2 3 5 4 1" etc. We just need to change the number of taken elements:

int main()
{ 
    permutation(0, 5, 5);
    return 0;
}

And output will be like bellow:

If we want to print only the permutation containing number 3 as first number than we need to modify permutation function like bellow:

void permutation(int level,int takenElement,int totalArrayElement)
{
    if(level == takenElement)
    {
        if(output[0] == 3)
            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;
        }
    }
}

Output would be like that:

Now we can solve UVA Problem 524 (Prime Ring Problem) by using this code. This problem is related to permutation. Try yourself first then click the bellow link for solution.

524 Prime Ring Problem Solution

216 Getting In Line

Divisible Sum Pairs: HackerRank

Combination:
Here bellow is the combination generation code by using recursion function. We will generate combination for the input 5,2,3,1,4. We will chose 3 numbers to generate combination among those 5 numbers.

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

using namespace std;

int input[5]= {5,3,4,2,1};
int output[25],visited[5];
void combination(int level,int pos,int takenElement,int totalArrayElement);
void printCombination(int takenElement);

int main()
{
    combination(0,0,3,5);
    return 0;
}

void combination(int level,int pos,int takenElement,int totalArrayElement)
{
    if(level == takenElement)
    {
        printCombination(takenElement);
        return;
    }

    if(pos>=totalArrayElement) return;

    output[level] = input[pos];

    combination(level+1,pos+1,takenElement,totalArrayElement);
    combination(level,pos+1,takenElement,totalArrayElement);
}

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

    cout << endl;
}

Output would be like bellow:

We can also modify this code as like as PERMUTATION code according to our need. Now find some UVA problem related to COMBINATION and try to solve using this code.

Friday, February 02, 2018

Permutation and Combination

No comments:

Post a Comment

BLOG INFO

Contact Form

POPULAR POST

LABELS

ARCHIVE

FEATURED Post

Followers

Visitor Locations

Visitor Locations