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();
}
/** 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.