Chittagong University of Enginnering and Technology, Bangladesh

ACMBEGINNER

 

Home\ Tutorial \ nCr

 Version 2.0
 Permutation And Combination    

/* nCm.cpp

   Implementation of calculation nCr

 

   Compiled : CYGNU & Microsoft Visual C++ 6.0

 

   Copyright 2003 by M H Rasel & CUET Old Sailor ; all rights reserved.

 

   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;

}

 

Copyright © 2003 M H Rasel
[Webmaster]
Last modified

1