Anagrams with regular expression

freecamellia

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.

aureshinite

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;
}

@

freecamellia

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

aureshinite

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.