## 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. IEEE Final Year projects Project Centers in Chennai are consistently sought after. Final Year Students Projects take a shot at them to improve their aptitudes. IEEE Final Year project centers ground for all fragments of CSE & IT engineers hoping to assemble.Final Year Projects for CSE

Spring Framework has already made serious inroads as an integrated technology stack for building user-facing applications. Spring Framework Corporate TRaining .

Specifically, Spring Framework provides various tasks are geared around preparing data for further analysis and visualization. Spring Training in Chennai

The Angular Training covers a wide range of topics including Angular Directives, Angular Services, and Angular programmability.Angular Training

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. Web designing trends in 2020

When we look into the trends, everything which is ruling today’s world was once a start up and slowly begun getting into. But Now they have literally transformed our lives on a tremendous note. To name a few, Facebook, Whats App, Twitter can be a promising proof for such a transformation and have a true impact on the digital world.

more details click the link now

[url]https://www.webdschool.com/web-development-course-in-chennai.html[/url]

5. Thanks for the interesting blog that you have implemented here. Very helpful and innovative. Waiting for your next upcoming article.
Mobile app development training
App development training
Mobile app development course
Mobile development course
Mobile application development course
Learn mobile application development

6. 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

7. Kaliteli escort bayanlarla tanışma fırsatı yakalamak için tıkla: ankara escort - ankara escort - ankara escort - ankara escort - ankara escort - ankara escort - ankara escort - ankara escort - ankara escort

8. 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

9. 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

10. Any power supply points past that demand the intervention of certified electricians to search for Hand Massagers errors in the power supply and ensure correct rectification. Due to their immense complexity, the efficiency of CNC machines could be compromised with incorrect power supply, such as using an incompatible socket. Chatter typically occurs from the workpiece or tool, making it essential to recognize its supply to make relevant changes. You can decrease the RPM of the spindle and allow the machinist to test totally different speeds discover out} a perfect setting.