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 *
   {
         pid = get_pthread_id()
         p = get_total_pthread()
         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 toreturn ;
} 

/* 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 --;
	 }
} 

/* Return total Permutation, for N-choose-R chooser */
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 nn", 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

*/ 

Leave a reply:

Your email address will not be published.

Site Footer