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.


17 comments:

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

      Delete
  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

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

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

    we have offered to the advanced syllabus course web design and development for available join now

    more details click the link now

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

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