## Saturday, July 19, 2014

### Permutations or combinations of "strings" and more ...

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
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 ^ (1100111000100110) = 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.

1. Thanks for the interesting blog that you have implemented here. Very helpful and innovative. Waiting for your next upcoming article.
Java Training in Chennai
Java Training Institute in Chennai
Java course in chennai
Java Training classes
Java Training
Java programming classes
core Java course

2. Nice post. Thanks for sharing! I want people to know just how good this information is in your article. It’s interesting content and Great work.
Digital Marketing Course In Kolkata

3. Thanks for this blog is very useful and unique

7 tips to start a career in digital marketing

“Digital marketing is the marketing of product or service using digital technologies, mainly on the Internet, but also including mobile phones, display advertising, and any other digital medium”. This is the definition that you would get when you search for the term “Digital marketing” in google. Let’s give out a simpler explanation by saying, “the form of marketing, using the internet and technologies like phones, computer etc”

more details click the link now

[url]https://www.webdschool.com/digital-marketing-course-in-chennai.html [/url]

4. It seems you are so busy in last month. The detail you shared about your work and it is really impressive that's why i am waiting for your post because i get the new ideas over here and you really write so well. good job
Ai & Artificial Intelligence Course in Chennai
PHP Training in Chennai
Ethical Hacking Course in Chennai Blue Prism Training in Chennai
UiPath Training in Chennai

5. Form Pilot - form filler software. It designed for filling in paper forms (of any type) on your computer. It makes typewriters obsolete.Exif Editor Windows

6. CLO Standalone Crack helps you adjust the quality and range of each to make your 3D canvases smoother and more impressive. It has all the new and unique .Clo Standalone 7.0 228