Important: Please read the Qt Code of Conduct - https://forum.qt.io/topic/113070/qt-code-of-conduct

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