Anagrams with regular expression



  • Hi all,
    What is the regular expression that represents all of anagrams of a string.
    For example:
    input string: "abc"
    output strings: "bca", "abc", "bac" ...

    This regular expression will be used with a QSortFilterProxyModel to display anagrams of a given string.



  • You want to use the regular expression to test strings or to generate strings? If you need to generate,
    you don't need a regular expression. You will have to write a code which generate all permutations from
    1 to input.length(), and use each permutation to create a new string.

    Anyway try this. the idea comes from creating the occurrence map. I let you test it properly:

    @

    #include <QtCore/QCoreApplication>
    #include <QMap>
    #include <QList>
    #include <iostream>
    #include <QRegExp>

    using namespace std;

    QString anagramRegexGenerator(const QString &input);

    int main(int argc, char *argv[])
    {
    QCoreApplication a(argc, argv);

    const QString s = "anagrams";
    
    QList<QString> list;
    list << "aangrams"
         << "granamas"
         << "anagrams"
         << "ngrmsaaa"
         << "magarans"
         << "an ag rams";// shound not passs
    
    QString regstring = anagramRegexGenerator(s);
    
    cout << " I found the expression :" << regstring.toStdString() <<endl;
    
    QRegExp regexp(regstring);
    
    if(regexp.isValid()){
    
        QString yes = "matches";
        QString no = "doesn't match";
        for(int i = 0; i < list.size(); i++){
            QString output;
            if(regexp.exactMatch(list[i])){
                output = yes;
            }
            else{
                output = no;
            }
            cout << list[i].toStdString()<<" "<<output.toStdString()<<" the regular expression" <<endl;
        }
    
    
    }
    
    return a.exec&#40;&#41;;
    

    }

    /** count the occurences of each character,

    • and create a string valid regex.
      */
      QString anagramRegexGenerator(const QString &input){
      QString lookaheadPart = "";
      QString matchingPart = "^";
      const QString positiveLookaheadPrefix="(?=";
      const QString positiveLookaheadSuffix=")";
      QMap<QChar,int> inputCharacterFrequencyMap;

      for ( int i = 0; i< input.length(); i++ )
      {
      if (!inputCharacterFrequencyMap.contains(input[i])) {
      inputCharacterFrequencyMap[input[i]] = 1;
      } else {
      ++inputCharacterFrequencyMap[input[i]];
      }
      }
      foreach(const QChar car,inputCharacterFrequencyMap.keys() ){
      lookaheadPart += positiveLookaheadPrefix;
      for (int k = 0; k< inputCharacterFrequencyMap[car]; k++) {
      lookaheadPart += ".*";
      if (car == ' ') {
      lookaheadPart += "\s";
      } else {
      lookaheadPart += car;
      }
      matchingPart += ".";
      }
      lookaheadPart += positiveLookaheadSuffix;
      }
      matchingPart += "$";
      return lookaheadPart + matchingPart;
      }

    @



  • I want filter a QSortFilterProxyModel, i.e. retrieve items that are anagrams of a given string.



  • Look at "this algorithm...":http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

    You need to sort the characters in the string (anagram becomes aaagmrn), and apply it.
    Best of luck.


Log in to reply
 

Looks like your connection to Qt Forum was lost, please wait while we try to reconnect.