fork(2) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. // assume we only work with lowercase letters from a to z
  8.  
  9. string words[] = {"pea", "nut", "butter", "peanut", "a", "but", "ten", "erupt"};
  10. const int WORD_COUNT = sizeof(words)/sizeof(words[0]);
  11. const int NUM_CHARS = 'z' - 'a' + 1;
  12. const int OTHER_CHARS = NUM_CHARS;
  13.  
  14. typedef int OccurrenceCount[NUM_CHARS + 1];
  15. typedef int BitMask;
  16.  
  17. const BitMask ONLY_OTHER_CHARS = (1 << OTHER_CHARS);
  18.  
  19. BitMask words_bm[WORD_COUNT];
  20. typedef vector<string> ResultType;
  21. ResultType anagramWords = ResultType();
  22.  
  23. // return a number in range 0..NUM_CHARS
  24. // OTHER_CHARS is a special code for characters not in 'a'..'z'
  25. inline int charCode(char c) {
  26. 	unsigned int code = c - 'a';
  27. 	return code > NUM_CHARS ? OTHER_CHARS : code;
  28. }
  29.  
  30. // BitMask = a bit mask of which characters exists in a string
  31. // it can be used as a quick word filter, 
  32. // i.e if a word contains character(s) which are not in the input string,
  33. // then it cannot be a word in the anagram
  34. BitMask getBitMask(const string& s) {
  35. 	BitMask result = ONLY_OTHER_CHARS;		// as we don't care about other characters, always set its bit to 1
  36. 	for (string::const_iterator iter = s.begin(); iter != s.end(); ++iter) {
  37. 		result |= (1 << charCode(*iter));
  38. 	}
  39. 	return result;
  40. }
  41.  
  42. BitMask getBitMask(const OccurrenceCount& oc) {
  43. 	BitMask result = ONLY_OTHER_CHARS;		// as we don't care about other characters, always set its bit to 1
  44. 	for (int i = 0; i < NUM_CHARS; ++i) {
  45. 		if (oc[i]) result |= (1 << i);
  46. 	}
  47. 	return result;
  48. }
  49.  
  50. void getOccurrenceCount(const string& s, OccurrenceCount& oc, bool zeroFill = true) {
  51. 	if (zeroFill) std::fill(oc, oc + NUM_CHARS, 0);
  52. 	for (string::const_iterator iter = s.begin(); iter != s.end(); ++iter) {
  53. 		++oc[charCode(*iter)];
  54. 	}
  55. }
  56.  
  57. void init()
  58. {
  59. 	for (int i = 0; i < WORD_COUNT; ++i) {
  60. 		words_bm[i] = getBitMask(words[i]);
  61. 	}
  62. }
  63.  
  64. void printOC(const OccurrenceCount& oc)
  65. {
  66. 	for (int i = 0; i <= NUM_CHARS; ++i) {
  67. 		if (oc[i] == 0) continue;
  68. 		cout << char('a' + i) << ": " << oc[i] << ", ";
  69. 	}
  70. 	cout << endl;
  71. }
  72.  
  73. void findAnagram(OccurrenceCount& oc, int startIndex = 0)
  74. {
  75. //	printOC(oc);
  76. 	BitMask bitmask = getBitMask(oc);
  77. 	if (bitmask == ONLY_OTHER_CHARS) {	// now the character pool is empty, i.e we have found an anagram
  78. 	    for (ResultType::iterator iter = anagramWords.begin(); iter != anagramWords.end(); ++iter)
  79. 	    	cout << *iter << " ";
  80. 	    cout << endl;
  81. 		return;
  82. 	}
  83.  
  84. 	for (; startIndex < WORD_COUNT; ++startIndex) {
  85. 		// filter words that contain characters not in input
  86. 		if ((bitmask | words_bm[startIndex]) != bitmask) continue;
  87.  
  88. 		const string& word = words[startIndex];
  89.  
  90. 		// update <oc> to exclude characters in <word>
  91. 		bool wordOk = true;
  92. 		for (string::const_iterator iter = word.begin(); iter != word.end(); ++iter) {
  93. 			if (--oc[charCode(*iter)] < 0) wordOk = false; 	// the character pool cannot allocate this word
  94. 		}
  95.  
  96. 		if (wordOk) {
  97. 			//cout << "-word: " << word << endl;
  98. 			anagramWords.push_back(word);
  99. 			findAnagram(oc, startIndex);
  100. 			// return the anagramWords to its original state
  101. 			anagramWords.pop_back();
  102. 		}
  103. 		// as with any backtracking algorithm, we have to recover the global states, in this case <oc>
  104. 		for (string::const_iterator iter = word.begin(); iter != word.end(); ++iter) {
  105. 			++oc[charCode(*iter)];
  106. 		}
  107. 	}
  108. }
  109.  
  110. int main() {
  111. 	init();
  112.  
  113. 	string inputString = "peanutbutterpeanutbutter";
  114. 	OccurrenceCount oc = {0};
  115. 	getOccurrenceCount(inputString, oc, false);
  116. 	findAnagram(oc, 0);
  117.  
  118. 	return 0;
  119. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
pea pea nut nut butter butter 
pea nut butter butter peanut 
pea nut butter a but ten erupt 
butter butter peanut peanut 
butter peanut a but ten erupt 
a a but but ten ten erupt erupt
https://ideone.com/vf7Rpl
http://stackoverflow.com/questions/38340871/efficient-algorithm-for-phrase-anagrams
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!