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
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 ^ (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.


9 comments:

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

    ReplyDelete
  2. 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”

    we have offered to the advanced syllabus course digital marketing for available join now

    more details click the link now

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

    ReplyDelete
  3. 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

    ReplyDelete
  4. 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

    ReplyDelete
  5. 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

    ReplyDelete