Adrian Lita

Generating all combinations of a string using the binary counter method

By: Adrian Lita

Published on: 2018-06-26

Keywords: #combinations #string #strings #binary-counter #academic #snippet #counter

 

Generating all k-combinations of n elements can be done in various ways. Here I'm preseting to you, for academic purpose, the binary counter method. First of all, let's calculate how many k-combinations of n exists: /* Calculates kCn kCn = n!/(k! * (n-k)!) */ unsigned int total_combinations(int n, int k) { //error if (k > n) { return 0; } unsigned int c = 1; //final result //check which one is greater,...

Read More >

Generating all permutations of a string with Heap's method

By: Adrian Lita

Published on: 2018-06-19

Keywords: #permutation #string #strings #academic #snippet #heap

 

Generating permutations can sometimes be a difficult task. The number of permutations is given by the factorial of the total number of elements: unsigned int total_permutations(unsigned int n) { unsigned int p = 1; for (int i = 2; i <= n; i++) { p *= i; } return p; } The function above only works to a n of about 12 on 32bit machines before the result exceeds that. So for n equals 12 we have about 479.001.600!!! permutations possible. For sure, that takes a lot of time to process. Anyhow,...

Read More >

Swapping numbers without the third variable

By: Adrian Lita

Published on: 2018-06-12

Keywords: #swapping #variables #academic #snippet #xorswap #xor

 

While not recommeded to be used in modern programming, this simple method allows swapping the values of 2 variables without the need of the third. Some caution should be taken into consideration, because this method works as long as both the variables that needed to be swapped are different (read: occupy different memory). void xorSwap(int *a, int *b) { *a = *a ^ *b; *b = *b ^ *a; *a = *a ^ *b; } This is the simplest variant of the xorSwap. Several...

Read More >