Results 1 to 9 of 9

Thread: Regular expression

  1. #1
    Join Date
    Dec 2011
    Posts
    7
    Thanked 2 Times in 2 Posts
    Qt products
    Qt4
    Platforms
    Windows

    Default Regular expression

    Hi all,
    What is the regular expression that represents all of strings constructed with only characters of an other string.
    For example:
    input string: "abc"
    output strings: "bca", "abc", "bac"
    ...

  2. The following user says thank you to QFreeCamellia for this useful post:

    thaihoangluu (30th December 2011)

  3. #2
    Join Date
    Mar 2011
    Location
    Russia, Lipetsk
    Posts
    17
    Thanked 6 Times in 6 Posts
    Qt products
    Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Regular expression

    Hello.
    I may be wrong, but it seems so:
    [abc]{3,}

  4. The following user says thank you to kunashir for this useful post:

    thaihoangluu (29th December 2011)

  5. #3
    Join Date
    Mar 2009
    Location
    Brisbane, Australia
    Posts
    7,546
    Thanks
    13
    Thanked 1,578 Times in 1,507 Posts
    Qt products
    Qt4 Qt5
    Platforms
    Unix/X11 Windows
    Wiki edits
    17

    Default Re: Regular expression

    You seem to want a good permutation algorithm. What are you trying to achieve? Regular expressions are used for matching patterns in text, and occasionally modifying matched segments, not generating whole new streams of data. Are you looking for anagrams of a given word in another list of words?

  6. The following user says thank you to ChrisW67 for this useful post:

    thaihoangluu (30th December 2011)

  7. #4
    Join Date
    Dec 2011
    Posts
    7
    Thanked 2 Times in 2 Posts
    Qt products
    Qt4
    Platforms
    Windows

    Default Re: Regular expression

    Quote Originally Posted by ChrisW67 View Post
    Are you looking for anagrams of a given word in another list of words?
    Yes exactly, like anagrams.

  8. The following user says thank you to QFreeCamellia for this useful post:

    thaihoangluu (30th December 2011)

  9. #5
    Join Date
    Mar 2009
    Location
    Brisbane, Australia
    Posts
    7,546
    Thanks
    13
    Thanked 1,578 Times in 1,507 Posts
    Qt products
    Qt4 Qt5
    Platforms
    Unix/X11 Windows
    Wiki edits
    17

    Default Re: Regular expression

    Kunashir's option will match strings like "aaa", "abb" etc. which are not anagrams of the original string.

    I don't know that you can do this in the general case with a single regular expression without literally listing every permutation. In cases of repeated characters you are able to collapse the list:
    Qt Code:
    1. "abc" => abc|acb|bac|bca|cab|cba // all the permutations
    2. "abc" => a(bc|cb)|b(ac|ca)|c(ab|ba) // a different arrangement of all permutations
    3.  
    4. "bob" => bob|bbo|obb|obb|bbo|bob // all the permutations, note the repeats
    5. "bob" => b(ob|bo)|obb // a simpler RE
    To copy to clipboard, switch view to plain text mode 
    The number of permutations rises rapidly with string length also. You may quickly find the limits of the regular expression engine.

  10. The following user says thank you to ChrisW67 for this useful post:

    thaihoangluu (30th December 2011)

  11. #6
    Join Date
    Sep 2009
    Location
    Wroclaw, Poland
    Posts
    1,391
    Thanked 342 Times in 324 Posts
    Qt products
    Qt4 Qt5
    Platforms
    MacOS X Unix/X11 Windows Android

    Default Re: Regular expression

    To check if string is anagram of given input you can always use brute-force algorithm that removes each character of input from string. In the end, if you are left with empty string, then it was a permutation of input characters. In pseudo-code:
    Qt Code:
    1. bool isAnagram( baseWord, toTest ){
    2. if( baseWord.length() != toTest.length() ) return false; // check obvious condition - cannot be a permutation if numbers of elements are not equal
    3. foreach( char c, baseWord ){
    4. toTest.removeExactlyOne(c);
    5. }
    6. return toTest.isEmpty();
    7. }
    To copy to clipboard, switch view to plain text mode 
    Not very good complexity ( O(N^2), N - number of chars in string ), but its better than nothing.

  12. The following user says thank you to stampede for this useful post:

    thaihoangluu (30th December 2011)

  13. #7
    Join Date
    Mar 2011
    Location
    Russia, Lipetsk
    Posts
    17
    Thanked 6 Times in 6 Posts
    Qt products
    Qt4
    Platforms
    Unix/X11 Windows

    Default Re: Regular expression

    ChirsW67, let me disagree with you.
    [abc] - It is any symbol from range ('a','b','c'), and repeated three times.
    I check it in "RegExp Planner".

  14. #8
    Join Date
    Sep 2009
    Location
    Wroclaw, Poland
    Posts
    1,391
    Thanked 342 Times in 324 Posts
    Qt products
    Qt4 Qt5
    Platforms
    MacOS X Unix/X11 Windows Android

    Default Re: Regular expression

    @kunashir:
    I think ChrisW67 is right:
    Qt Code:
    1. #include <QDebug>
    2. #include <QRegExp>
    3.  
    4. int main(int argc, char **argv) {
    5. QRegExp ex("[abc]{3,}");
    6. qDebug() << ex.exactMatch("aaa");
    7. return 0;
    8. }
    To copy to clipboard, switch view to plain text mode 
    prints 'true'.

    Another algorithm I can think of, is to use O( n log(n) ) sorting method, eg. merge sort, something like:
    Qt Code:
    1. bool isAnagram(baseWord, toTest){
    2. if( baseWord.length() == toTest.length() ){
    3. return sort(baseWord) == sort(toTest);
    4. }
    5. return false;
    6. }
    To copy to clipboard, switch view to plain text mode 
    Complexity of this algorithm is the same as sorting method (string equality test should be linear), so its better than my previous suggestion.

  15. #9
    Join Date
    Mar 2009
    Location
    Brisbane, Australia
    Posts
    7,546
    Thanks
    13
    Thanked 1,578 Times in 1,507 Posts
    Qt products
    Qt4 Qt5
    Platforms
    Unix/X11 Windows
    Wiki edits
    17

    Default Re: Regular expression

    @kunashir: Your regular expression is perfectly fine but it doesn't quite answer the question posed. An anagram uses all the letters of the original word in another order.


    There might be something of use here. I haven't tested that code though.

Similar Threads

  1. Regular expression help!
    By ConkerX in forum Qt Programming
    Replies: 10
    Last Post: 31st August 2011, 15:47
  2. Help with regular expression
    By Gourmet in forum General Programming
    Replies: 19
    Last Post: 11th August 2011, 15:04
  3. Regular Expression Problem
    By kaushal_gaurav in forum Qt Programming
    Replies: 2
    Last Post: 27th February 2009, 09:41
  4. Regular expression in QLineEdit?
    By vishal.chauhan in forum Qt Programming
    Replies: 3
    Last Post: 1st October 2007, 10:58
  5. Find with Regular Expression?
    By vishal.chauhan in forum Qt Programming
    Replies: 1
    Last Post: 1st August 2007, 14:44

Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Digia, Qt and their respective logos are trademarks of Digia Plc in Finland and/or other countries worldwide.