Combination

comb

/**
=================================================================
Author        : Prakash Gautam (068/BEX/429) (fb.com/pranphy/)
Date Created  : 12-12-2012 (12-12-12)
Last Updated  : 12-12-2012
=================================================================
*/
#include

void combn(char*,int,int);
void init_sub_ary(int*sub_ary,int r,int k, int cell_value);
void output(char*,int*,int);

int main()
{
    int n,r;
    char* ary;
    printf("Prakash [(fb.com/pranphy ^^ pranphy.wordpress.com) (068/BEX/429)]  \n");
    printf("\n This program prints all the combination C(n,r) \nfor given n and r for a given string \n");
    printf("\nEnter the value of n                       : ");
    scanf("%d",&n);
    ary=malloc(n*sizeof(char));
    printf("Enter the string to find combination\n(should be longer or equal to n)           : ");
    scanf("%s",ary);
    printf("Enter the value of r                       : ");
    scanf("%d",&r);
    combn(ary,n,r);
    return 0;
}
void combn(char*ary,int n,int r)
{
    int k,cell_value=0, max_cell_value=0;
    int*sub_ary=malloc(r*sizeof(int));
    init_sub_ary(sub_ary,r,0, 0);
    do
    {
        k=r-1;
        while(*(sub_ary+k)<n)
        {
            output(ary,sub_ary,r);
            (*(sub_ary+k))++;
        }
        do
        {
            k--;
            cell_value=*(sub_ary+k);
            max_cell_value=n-r+k;
        }
        while(cell_value==max_cell_value);
        init_sub_ary(sub_ary,r,k,cell_value+1);
    }
    while(*(sub_ary)<=n-r);
}
void output(char* ary, int*sub_ary,int r)
{
    int cnt;
    for(cnt=0;cnt<r;cnt++)
        printf("%c",*(ary+*(sub_ary+cnt)));
    printf("\n");
}
void init_sub_ary(int*sub_ary,int r,int k, int cell_value)
{
    int cnt;
    for(cnt=k;cnt<r;cnt++)
        *(sub_ary+cnt)=cell_value++;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s