とくにあぶなくないRiSKのブログ

危ないRiSKのブログだったかもしれない。本当はRiSKだけどググラビリティとか取得できるIDの都合でsscriskも使ったり。

すべてのアナグラムグループを検索するプログラム

STL―標準テンプレートライブラリによるC++プログラミング 第2版
単語辞書 を調べ,すべてのアナグラムを表示するプログラム。
単語を sort としたのものを追加情報として pair.first に持つ(単語そのものはpair.second に入れる)。で,pair.first をキーに全項目を sort すると同じアナグラムを持つ単語が固まる。最後に adjacent_find と find_if で同じアナグラムの固まりの範囲(j, k]を探し,それを copy で cout へ出力。出力の際の起こる PS から std::string への型変換は PS の中で定義してる。

// ps.hpp

// 223a
#include<utility>
#include<string>
#include<algorithm>
struct PS: std::pair<std::string, std::string>
{
 PS()
  : pair<std::string, std::string>()
 {}
 PS(const std::string& s)
  : pair<std::string, std::string>(s, s)
 {
  sort(first.begin(), first.end());
 }
 operator std::string()const{return second;}
};
// 223b
#include<functional>
struct FirstLess: std::binary_function<PS, PS, bool>
{
 bool operator()(const PS& p, const PS& q)const{
  return p.first < q.first;
 }
};
// 224a
struct FirstEqual: std::binary_function<PS, PS, bool>
{
 bool operator()(const PS& p, const PS& q)const{
  return p.first == q.first;
 }
};
// P225 ex13-01.cpp
#include<iostream>
#include<string>
#include<fstream>
#include<iterator>
#include<vector>
#include<algorithm>
#include<functional>
#include"ps.hpp"
int main(){
 using std::cout;
 using std::flush;
 using std::string;
 using std::cin;
 using std::ifstream;
 using std::endl;
 using std::istream_iterator;
 using std::vector;
 using std::copy;
 using std::back_inserter;
 using std::adjacent_find;
 using std::find_if;
 using std::not1;
 using std::bind1st;
 using std::ostream_iterator;
 cout << "Anagram group finding program:\n"
  "finds all anagram groups in a dictionary.\n\n"
  "First, enter the name of the file containing\n"
  "the dictionary: " << flush;
 string dictionaryName;
 cin >> dictionaryName;
 ifstream ifs(dictionaryName.c_str());
 if(!ifs.is_open()){
  cout << "Eh? Could not open file named " << dictionaryName << endl;
 }
 cout << "\nReading the dictionary ..." << flush;
 istream_iterator<string> strIter(ifs), strEnd;
 vector<PS> wordPairs;
 copy(strIter, strEnd, back_inserter(wordPairs));
 cout << "\nSearching " << wordPairs.size() <<
  " words for anagram groups..." << flush;
 sort(wordPairs.begin(), wordPairs.end(), FirstLess());
 vector<PS>::iterator j = wordPairs.begin(),
  finis = wordPairs.end(), k;
 cout << "\n\nThe anagram groups are:" << endl;
 for(;;){
  j = adjacent_find(j, finis, FirstEqual());
  if(j == finis)break;
  k = find_if(j + 1, finis, not1(bind1st(FirstEqual(), *j)));
  cout << "  ";
  copy(j, k, ostream_iterator<string>(cout, " ")); cout << endl;
  j = k;
 }
}