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.

## No comments:

## Post a Comment