# N-choose-R

### Simple Solution for creating Permutations

While working on a research project, i came across a simple task of creating sets of permutation for a given objects. What i thought simple task become tedious after goggling it. I didn’t find any simple solutions for creating a permutations. So i create his one for those who wants simple solution for creating permutations.

#### How to solve complicated problems of creating permutation.

• Creating permutation of object such as set of colors, basically the task is to find combination of colors (i.e. color addition problem)

Step 1 : create array of pointers to color objects

colors = { red, green, blue, red, …}

Step 2 : create method which take color object pointers and return a combination for selected color objects

magenta = combinations(colors, indexes), where indexes contain index of red and blue indexes = {2, 3}

Step 3 : create indexes using Permutation methods.

• Creating unique distribution of samples across multiple threads (p-threads) , .e. Dividing the work across the threads such that none of the thread do the same work.
```
int n;//  set of object
int r; //  subset of chosen object

\* for each threads do *\
{
perm =  createPermutation(n , r)
startindex = pid * (n / p)
PermuteAfterNiteration (perm, startindex)

/*
use nextpermutation method which return unique index
Performed required operations
*/

freepermutation()
}

Code :

#include <stdio.h>;
#include <stdlib.h>;
#include <string.h>;

struct Permutation {

/* To Store current Combinations */
int *A_i ;

/* To Store previous Combinations */
int *A_i_1 ;

/* Total Number of Objects ( i.e. N), Object to Choose (i.e. R) */
int n, r ;

/* To Store total possible Combinations */
long int noOfPermutationCompleted ;
};

/* Create N-Choose-R chooser */
struct Permutation *createPermutation ( int n , int r ){

int i ;
struct Permutation * toreturn = ( struct Permutation *) malloc( sizeof ( struct Permutation ));
toreturn -> n = n ;
toreturn -> r = r ;
toreturn -> noOfPermutationCompleted = 0 ;
toreturn -> A_i = malloc ( r * sizeof ( int ));
toreturn -> A_i_1 = malloc ( r * sizeof ( int ));
for ( i = 0 ; i < r ; i ++){
toreturn -> A_i [ i ] = 0 ;
toreturn -> A_i_1 [ i ] = 0 ;
}
}

/* Return next array of object indexs */
int * nextPermutation ( struct Permutation * Per ){

int j ;
size_t bytes = ( sizeof ( int ) * Per -> r - 1 );

/* Per -> A_i = Per -> A_i_1; */
memcpy ( Per -> A_i_1 , Per -> A_i , bytes );

for ( j = ( Per -> r - 1 ) ; j >;= 0 ; j --){
Per -> A_i [ j ] += 1 ;
if ( Per -> A_i [ j ] < Per -> n )
break ;
else
Per -> A_i [ j ] = 0 ;
}

/* Per -> A_i = Per -> A_i_1; */
memcpy ( Per -> A_i_1 , Per -> A_i , bytes );

Per -> noOfPermutationCompleted += 1 ;

return Per -> A_i ;
}

/* It initialise N-Choose-R chooser to start after Nth Iteration */
void PermuteAfterNiteration ( struct Permutation * Per , long int Niteration ){

while ( Niteration != 0 ){
nextPermutation ( Per );
Niteration --;
}
}

long int TotalPermutations ( struct Permutation * Per ){

long int ret = 1 ;
int i = 0 ;

for ( i = 0 ; i < Per -> r ; i ++)
ret *= Per -> n ;

return ret ;
}

/* Free Memory */
void free_Permutation ( struct Permutation * Per ){

free ( Per -> A_i );
free ( Per -> A_i_1 );
free ( Per );
}
/*
Demo Program

int main(){

int j, *permute, N = 4, R = 2, Nth = 10;
long int tot, i;

struct Permutation *Per = createPermutation(N, R);

tot = TotalPermutations(Per);

printf("Total Permutation %ld \n\n", tot);
printf("List all Permutations \n");
for(i = 0 ; i < tot ; i++){
permute = nextPermutation(Per);
printf("permutation %ld : ",i + 1);
for(j = 0 ; j < R ; j++)
printf("%d ", permute[j]);
printf("\n");
}

printf("\nAfer Using nth Iterator \n");
PermuteAfterNiteration(Per, Nth);
printf("List all Permutations \n");
for(i = 0 ; i < tot - Nth ; i++){
permute = nextPermutation(Per);
printf("permutation %ld : ",i + 1);
for(j = 0 ; j < R ; j++)
printf("%d ", permute[j]);
printf("\n");
}

printf("Free Memory \n");
free_Permutation(Per);

return 0;
}

Output :
Total Permutation 16

List all Permutations
permutation 1 : 0 1
permutation 2 : 0 2
permutation 3 : 0 3
permutation 4 : 1 0
permutation 5 : 1 1
permutation 6 : 1 2
permutation 7 : 1 3
permutation 8 : 2 0
permutation 9 : 2 1
permutation 10 : 2 2
permutation 11 : 2 3
permutation 12 : 3 0
permutation 13 : 3 1
permutation 14 : 3 2
permutation 15 : 3 3
permutation 16 : 0 0

Afer Using nth Iterator
List all Permutations
permutation 1 : 2 3
permutation 2 : 3 0
permutation 3 : 3 1
permutation 4 : 3 2
permutation 5 : 3 3
permutation 6 : 0 0

Free Memory

*/