Tuesday, March 11, 2008

The most permutable word is "trace"?

Which English word has the most permutations which are also English words? (Of course each of the lexible permutations is also an answer. Is "lexible" a sensible term for having the property of being a word?)

Here's some C++ code to look at this:
most_permutable.cpp:
#include <algorithm>
#include <cctype>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <string>
using namespace std;

template<typename T>
class select2nd {
public:
typedef T argument_type;

typename T::second_type operator()(const T& t) {
return t.second;
}
};

template<typename B, typename U1, typename U2>
class binary_compose {
public:
typedef typename B::result_type result_type;
typedef typename U1::argument_type arg1_type;
typedef typename U2::argument_type arg2_type;
binary_compose(const B& b, const U1& u1, const U2& u2) :
b(b), u1(u1), u2(u2) {}

result_type operator()(const arg1_type& x1,
const arg2_type& x2)
{
return b(u1(x1), u2(x2));
}

private:
B b;
U1 u1;
U2 u2;
};

template<typename B, typename U1, typename U2>
binary_compose<B, U1, U2>
compose2(B b, U1 u1, U2 u2)
{
return binary_compose<B, U1, U2>(b, u1, u2);
}

typedef map<string, int>::iterator iter;

int main(int numArgs, char** args)
{
map<string, int> permutationCounts;
ifstream in("/usr/share/dict/words");
while (in) {
string word;
in >> word;
if (!word.empty() && islower(word[0])) {
sort(word.begin(), word.end());
iter p = permutationCounts.find(word);
if (p != permutationCounts.end()) {
++(*p).second;
}
else {
permutationCounts.insert(make_pair(word, 1));
}
}
}

iter m = max_element(permutationCounts.begin(),
permutationCounts.end(),
compose2(less<int>(),
select2nd<pair<string, int> >(),
select2nd<pair<string, int> >()));
cout << (*m).first << " with " << (*m).second << '\n';
}

Drum roll:

$ g++ -Wall most_permutable.cpp
$ ./a.out
acert with 9


What are the 9?
find_perm.cpp:
#include <algorithm>
#include <cstdio>
#include <fstream>
#include <iostream>
#include <string>
using namespace std;

int main(int numArgs, char** args)
{
if (numArgs != 3) {
cerr << "Usage: find_perm <file> <letters>\n";
return 1;
}

ifstream in(args[1]);
if (!in) {
cerr << "Problem opening " << args[1] << '\n';
perror("");
return 1;
}

string letters(args[2]);
sort(letters.begin(), letters.end());
const string::size_type n = letters.size();

string word;
while (in) {
in >> word;

if (n == word.size()) {
string key(word);

sort(key.begin(), key.end());

if (key == letters) {
cout << word << '\n';
}
}
}

in.close();

}


$ g++ -Wall -o find_perm find_perm.cpp
$ ./find_perm oops
Usage: find_perm <file> <letters>
$ ./find_perm oops oops
Problem opening oops
No such file or directory
$ ./find_perm /usr/share/dict/words trace
caret
carte
cater
crate
creat
creta
react
recta
trace


What the heck is "creat"? Hm. Google doesn't know about it. It is really there though:
$ grep -w -n creat /usr/share/dict/words
45105:creat

No comments: