C Program to find Permutation and Combination

The C program to find permutation and combination solves 4 different types of problems. The permutation problems are arrangement problems and the combination problems are selection problems. You will more details about each type of problem in the problem definition section.

The list of problems are given below.

  1. R-permutation of a set of N distinct objects where 1 < R < N.
  2. R-permutation of a set of N distinct objects with repetition allowed.
  3. Permutation of N objects where N is not distinct and contains indistinguishable objects of different types – n1 types, n2 types, … , nk types.
  4. R-combination of a set of N distinct objects where 1 < R < N.
  5. R-combination of a set of N distinct objects with repetition allowed.

You must be familiar with following concepts before learn from this examples.

Problem Definition : R-permutation of N distinct objects

Permutation is the number of arrangement of N distinct objects taken R at a time. Suppose we have N people sitting in a row of chairs, how many ways to change the sitting arrangement taken R people at a time.

For example, suppose we have 3 men sitting on 3 chairs; let’s call them A, B and C. The number of arrangement of 2 men out of 3 i.e., N =3, R = 2 is given below.

AB          AC          BC  BA          CA          CB

In the above example, order of the arrangement matters and each of these different orders are counted

Formula for Permutation = N factorial/ (N-R) factorial    NPR = N! / (N-R)!

Flowchart 1 – Permutation without Repetition

Flowchart - Permutation - No Repetition
Flowchart – Permutation – No Repetition

Program Code – Permutation No Repetition

The C program for permutation of numbers is given below.

#include <stdio.h>    #include <conio.h>    int fact(int);    int main()  {        int NPR,N,R,M,i;        NPR=0;        M=0;        M= N-R;        printf("Enter value for N and R:");        scanf("%d %d",&N,&R);        NPR = fact(N)/fact(M);        for(i=0;i<45;i++)        printf("_");printf("\n\n");        printf("Number of %d-permutation of %d object = %dn",R,N,NPR);        for(i=0;i<45;i++)        printf("_");printf("\n\n");        system("PAUSE");        return 0;    }    int fact(m)  {        int i,fact=1;        for(i=1;i<=m;i++)      {            fact=fact*i;        }        return(fact);    }    

Output

The output of the first program is given below.

Output 1 - Permutation With No Repetition
Output 1 – Permutation With No Repetition

Problem Definition : R-permutation of a set of N distinct objects with repetition allowed

In permutation without repetition, you select R objects at a time from N distinct objects. Now you have R positions to arrange N objects.

First position can have N choices    Second position can have ( N-1 ) choices.    Third position can have (N - 2) choices.    ...    ...    Rth position can have ( N - R + 1 ) choices.  

For example

Let’s N = 6, R = 3

1st Position   2nd Position   3rd Position    6 choices  x   5 choices    x 4 choices       =  120

However, with permutation with repetition allowed, the above example becomes

1st Position   2nd Position   3rd Position         6 choices   x  6 choices   x  6 choices =  6^3 =  216

In other words, the N objects are repeated R times = N^R

Advertisements


Flowchart 2 – Permutation with repetition allowed

Flowchart - Permutation With Repetition Allowed
Flowchart – Permutation With Repetition Allowed

Program Code – Permutation with repetition allowed

The C program for permutation with repetition allowed is given below.

/* program to find npr = n^r */    #include <math.h>    #include <stdio.h>    #include <conio.h>    main()  {        int i,N,R,NPR;        NPR =1;        printf ("Enter the values for N and R:");        scanf ("%d %d", &N, &R);        for(i=0;i<R;i++)      {            NPR = NPR * N;        }        for(i=0;i<50;i++)        printf("_");printf("\n\n");        printf("Number of %d-permutation of %d with Repetition = %d\n",R,N,NPR);        for(i=0;i<50;i++)        printf("_");printf("\n\n");        system("PAUSE");        return 0;    }

Output 2

The output of the program for permutation with repetition allowed is given below.

Output 2 - Permutation With Repetition Allowed
Output 2 – Permutation With Repetition Allowed

Problem Definition : Permutation of N objects where N is not distinct and contains indistinguishable objects

Another type of permutation problem is when you have N object, but they are not distinct and contains many objects of similar types.

N objects =   x object of  n1 type +   y  object of n2 type +   z object of n3 type +   ... +   p objects of nk type

The formula is given by following

N = n1 + n2 + n3 + ... + nk

To find permutation of N objects where some of them of indistinguishable, you use following.

NPR = N! / (n1! + n2! + n3!)

Flowchart 3 – Permutation of Indistinguishable Objects

Flowchart - Permutation of Indistinguishable Objects
Flowchart – Permutation of Indistinguishable Objects

Program Code – Permutation of Indistinguishable Objects

The C program for permutation of  numbers where some objects are indistinguishable.

#include <stdio.h>    #include <conio.h>    #include<math.h>    int fact(int);    main()  {      int i,N,TOT,NPR,SUB;        int OBJ[15];        SUB = 1;TOT = 0;        printf ("Enter the values for number of object N:");        scanf("%d",&N);    for(i=1;i<=N;i++)  {        printf("How many number of object OBJ[%d]?:",i);        scanf ("%d", &OBJ[i]);    }    for(i=1;i<=N;i++)  {        TOT = TOT + OBJ[i];    }    for(i=1;i<=N;i++) {         if(OBJ[i]>1)        SUB = SUB * fact(OBJ[i]);    }        NPR = fact(TOT)/SUB;        for(i=0;i<50;i++)        printf("_");        printf("\n\n");        printf("Permutation of %d distinguishable objects = %d\n",N,NPR);        for(i=0;i<50;i++)        printf("_");printf("\n\n");        system("PAUSE");        return 0;    }    int fact(m)  {        int i,fact=1;        for(i=1;i<=m;i++)      {            fact=fact*i;        }        return(fact);    }

Output 3

The output of program with permutation is given below.

Output 3 - Permutation of indistinguishable Objects
Output 3 – Permutation of indistinguishable Objects

Problem Definition : R-combination of a set of N distinct objects

Combination is selection of N distinct object taken R at a time. The word “Selection” is very important because it indicates that only a particular order of R objects is accepted.

For example, consider our example of permutation of A,B and C.

AB          AC          BC    BA         CA           CB

Here only one of the arrangement is “selected”, you can only select AB or BA, not both. This is called a Combination.

Formula for nCr is given below.

Formula for Combination = N factorial / (R factorial * (N-R) factorial)
NCR = N!/(R! * (N-R)!)

Flowchart 4 – Combination No Repetition

Flowchart - Combination No Repetition
Flowchart – Combination No Repetition

Program Code – Combination No Repetition

C program for combination of numbers is given below.

/* program to find nCr */    #include <stdio.h>    #include <conio.h>    long int fact(long int);    int main()  {        long int i,N,R,M,NCR;        printf ("Enter the values for N and R: ");        scanf ("%d %d", &N, &R);        M = N - R;        NCR = fact(N)/(fact (R) * fact(M)); //ncr formula        for(i=0;i<45;i++)        printf("_");printf("\n\n");        printf("Number of %d-combination of %d = %dn",R,N,NCR);        for(i=0;i<45;i++)        printf("_");printf("\n\n");        system("PAUSE");        return 0;    }    long int fact(long int m)  {        long int i,fact=1;        for(i=1;i<=m;i++)      {            fact=fact*i;        }        return(fact);    }

Output 4

The output of the program is given below.

Output 4 - Combination With Repetition
Output 4 – Combination With Repetition

Problem Definition : R-combinations of a set of N distinct object with repetition allowed

We know that R-combination is selection of R objects at a time from given N object set. The R-combination of a set of N distinct object with repetition means that we can now select each object in N more than once.

For example, Let’s N = 3, with A, B and C and R=2

You need to select 2 object combination out of 3 such that you can now choose any object more than once.

AA   AB    AC   BB    BC    CC

The formula for R-combination with repetition is given below.

nCr formula with repetition

NCR = (N + R - 1)/ ( R! * (N - 1)!)

The solution to the above problem is

4 2 * 3 * 2 * 1
————–               =  6
2 * 1 * 2 * 1 

Flowchart 5 – Combination With Repetition Allowed

Flowchart - Combination Repetition Allowed
Flowchart – Combination Repetition Allowed

Program Code – Combination With Repetition Allowed

The C program for combination of numbers with repetition allowed is given below.

/* program to find nCr with repetition */    #include <stdio.h>    #include <conio.h>    int main()  {        int N,R,P,M,fact(int);        int i,NCR;        printf ("Enter the value for N and R: ");        scanf ("%d %d", &N, &R);        P = N + R - 1;        M = P - R;        NCR = fact(P)/(fact(R)* fact(M));        for(i=0;i<45;i++)        printf("_");printf("\n\n");        printf("Number of %d-Combination of %d with Repetition = %d\n",R,N,NCR);        for(i=0;i<45;i++)        printf("_");printf("\n\n");        system("PAUSE");        return 0;  }    int fact(p)  {        int i,fact=1;        for(i=1;i<=p;i++)      {            fact=fact*i;        }        return(fact);  }

Output 5

The output of the program is given below.

Output 5 - Combination With Repetition Allowed
Output 5 – Combination With Repetition Allowed

Related Articles:

Advertisements