fbpx

C++: Anagrams

Bjarne-stroustrup
 

Two or more words can be composed of the same characters, but in a different order. Using the word list at http://www.puzzlers.org/pub/wordlists/unixdict.txt, find the sets of words that share the same characters that contain the most words in them.

#include <iostream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
	std::ifstream in("unixdict.txt");
	typedef  std::map<std::string, std::vector<std::string> > AnagramMap;
	AnagramMap anagrams;

	std::string word;
	size_t count = 0;
	while (std::getline(in, word)) {
		std::string key = word;
		std::sort(key.begin(), key.end());
		// note: the [] op. automatically inserts a new value if key does not exist
		AnagramMap::mapped_type & v = anagrams[key];
		v.push_back(word);
		count = std::max(count, v.size());
	}

	in.close();

	for (AnagramMap::const_iterator it = anagrams.begin(), e = anagrams.end();
	it != e; it++)
	if (it->second.size() >= count) {
		std::copy(it->second.begin(), it->second.end(),
		std::ostream_iterator<std::string>(std::cout, ", "));
		std::cout << std::endl;
	}
	return 0;
}
Output:
abel, able, bale, bela, elba, 
caret, carte, cater, crate, trace, 
angel, angle, galen, glean, lange, 
alger, glare, lager, large, regal, 
elan, lane, lean, lena, neal, 
evil, levi, live, veil, vile,

SOURCE

Content is available under GNU Free Documentation License 1.2.