Imagine you want to implement a password policy.
You want to make sure that a user does not use a permutation of his previous password (case sensitive).
The first trivial thing we notice is that
- If one password is a permutation of the other then they have the same length.
We try to implement an efficient solution using xor.
We use the fact that x ^ x == 0.
The complexity is O(n) to figure out if character array a is a permutation of character array b.
As a reminder:
O(1) < O(lg n) < O(n) < O(n lg n) < O(n^2) < O(2^n) < O(n!)
If you would consider to sort the "string" and then to compare it then it would have
a complexitey of O(n log n) + O(n) = O((n log n) + n) = max(O(n log n) , O(n)) = O(n log n).
//returns 0 if a and b are permutations of each other, a value > 0 otherwise int is_perm(char *a , char *b) { int la = 0 ; int lb = 0 ; int i = 0 ; int check = 1 ; if(a == NULL || b == NULL) return(0) ; la = (int)strlen(a) ; lb = (int)strlen(b) ; if(la == 0 || lb == 0) return(0) ; if(la != lb) return(1) ; check = (a[0] ^ b[0]) ; for(i = 1 ; i < la ; i++) { check = (check ^ (a[i] ^ b[i])) ; } return(check) ; }How does it work?
Let's try an example by hand:
Let a = "das" and b = "sad" and c = "des"
das = 00100110 10000110 11001110
sad = 11001110 10000110 00100110
des = 00100110 10100110 11001110
Let's call is_perm(a , b)
count = 'd' ^ 's' = 00100110 ^ 11001110 = 11101000
count = (count ^ ('a' ^ 'a')) = 11101000 ^ 00000000 = 11101000
count = (count ^ ('s' ^ 'd')) = 11101000 ^ (11001110 ^ 00100110) = 00000000
count is 0, that means character array a is a permutation of character array b.
Let's call is_perm(a , c)
count = 'd' ^ 'd' = 00100110 ^ 00100110 = 00000000
count = (count ^ ('a' ^ 'e')) = 00000000 ^ (10000110 ^ 10100110)
= 00000000 ^ 00100000 = 00100000
count = (count ^ ('s' ^ 's')) = 00100000 ^ 00000000 = 00100000
count is 4, that means character array a is not a permutation of character array c.
Good luck in finding permutations.