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 \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 */
