Home\ Tutorial \ nCr Version 2.0
 Permutation And Combination

/* nCm.cpp

Implementation of calculation nCr

Compiled : CYGNU & Microsoft Visual C++ 6.0

Permission is granted for use in non-commerical applications provided this copyrightnotice   remains intact and

unchanged.

*/

#include<stdio.h>

#include<math.h>

/* *********************************************** */

/*      Calculate nCm           */

/*      Input : Two integer number n m        */

/*      Return : The nCm          */

/* *********************************************** */

double nCr(int n,int m)

{

int k;

register int i,j;

double c,d;

c=d=1;

k=(m>(n-m))?m:(n-m);

for(j=1,i=k+1;(i<=n);i++,j++)

{

c*=i;

d*=j;

if( !fmod(c,d)  && (d!=1) )

{   c/=d;

d=1;

}

}

return c;

}

/* A sample main function */

main(void)

{

int n,m;

while(scanf("%d%d",&n,&m)!=EOF)

printf("%.0lf\n",nCr(n,m));

return 0;

}

Another way to calculate the nCm by using the Pascal's triangel. The following program use this.

#include<stdio.h>

#define MAXTRI 50

unsigned long int pas[MAXTRI][MAXTRI];

void pascals(int n)

{

register int i,j;

pas[0][0]=1;

pas[1][0]=pas[1][1]=1;

for(i=2;i<=n;i++)

{

pas[i][0]=1;

for(j=1;j<i;j++)

{

pas[i][j]= pas[i-1][j-1]+pas[i-1][j];

}

pas[i][j]=1;

}

}

main(void)

{

pascals(10);

int n,m;

while(scanf("%d%d",&n,&m)!=EOF)

{

printf("%lu",pas[n][m]);

}

return 0;

}

In the case of repeated object:------

If in a word of s length character, a character is repeated l times, then the number of arrangement is:

If there is more then one repeated character the we can write,

where,
l1,
is the repeation times of  first repeated character.
l2, is for second repeated character
and, so on…

but remember calculating both n! and l1!* l2! * l3!* ….. *ln may occurs overflow. So I use

The code of this type of combination is as follows:

` `

#include<stdio.h>

#include<math.h>

#include<string.h>

#define MAX 30

/* *************************************************************** */

/* A sample function that calculate how many ways that you can     */

/*  rearrange a word with its letter                         */

/* *************************************************************** */

double test(char *str)

{

int de[MAX]={0};

int ss[300] = {0};

int l = strlen(str);

int i,j=0;

double c=1,d=1;

for(i=0;i<l;i++)

{

ss[str[i]]++;

if(ss[str[i]] > 1)

de[j++] = ss[str[i]];

}

c = 1;

for(i=2;i<=l;i++)

{

c*=i;

if(j>0)

d*= de[--j];

if((d!=1) && !(fmod(c,d)))

{

c /= d;

d=1;

}

}

return c;

}

/* A sample main function */

main(void)

{

char word[MAX];

int n;

int j=0;

scanf("%d",&n);

for(;n>0;n--)

{

scanf("%s",word);

printf("Data set %d: %.0f",++j,test(word));

//          if(n!=1)

putchar('\n');

}

return 0;

}

 Related Problems 369 Combinations 10219 Find the ways ! 10338 Mischievous Children
 ProblemSet Tricks | Reference | Tutorial FAQ|Index|Info Credits|Guestbook|Update