From: philgarofalo_at_[hidden]
Date: 2008-01-12 14:48:12
Author: pgarofalo
Date: 2008-01-12 14:48:11 EST (Sat, 12 Jan 2008)
New Revision: 42704
URL: http://svn.boost.org/trac/boost/changeset/42704
Log:
Updated the example and test applications. They now properly refer to the new combinatorial function names and the minimal Boost test library.
Text files modified:
sandbox/libs/sequence_algo/example/combinatorial_ex1.cpp | 137 +++++++++++++++++++--------------------
sandbox/libs/sequence_algo/example/combinatorial_ex2.cpp | 116 +++++++++++++++++++--------------
2 files changed, 135 insertions(+), 118 deletions(-)
Modified: sandbox/libs/sequence_algo/example/combinatorial_ex1.cpp
==============================================================================
--- sandbox/libs/sequence_algo/example/combinatorial_ex1.cpp (original)
+++ sandbox/libs/sequence_algo/example/combinatorial_ex1.cpp 2008-01-12 14:48:11 EST (Sat, 12 Jan 2008)
@@ -1,7 +1,7 @@
-// combinatorial_ex1.cpp -- Test program for r-permutation and r-combination generic functions
+// combinatorial_ex1.cpp -- Test program for partial permutation and partial combination generic functions
// in combinatorial.h.
-// Copyright © Philip F. Garofalo 2002. All rights reserved.
+// Copyright © Philip F. Garofalo 2008. All rights reserved.
// Permission to copy, use, modify, sell and distribute this software
// is granted provided this copyright notice appears in all copies.
// This software is provided "as is" without express or implied
@@ -20,7 +20,6 @@
#include <string>
#include <fstream>
#include <stdexcept>
-using namespace std;
#ifdef __MWERKS__
#include <console.h>
@@ -41,7 +40,7 @@
// partial template specialization, so we'll need to explicitly specialize
// iterator_traits for the container type, which is char* in this test app.
// It is required only before the call to the default version of
-// prev_r_permutation,the one without the user-supplied compare function.
+// prev_partial_permutation,the one without the user-supplied compare function.
//
namespace std {
template<>
@@ -57,56 +56,47 @@
// PrintLetters ---------------------------------------------------------//
-
-
-
// This function prints a line of letters with a vertical bar
-
// separating the the first r letters from the remainder.
-
inline void PrintLetters(int r)
{
- copy(numerals, numerals + r, ostream_iterator<char>(cout, " "));
- cout << "| ";
- copy(numerals + r, numerals + DIM(numerals), ostream_iterator<char>(cout, " "));
- cout << '\n';
+ std::copy(numerals, numerals + r, std::ostream_iterator<char>(std::cout, " "));
+ std::cout << "| ";
+ std::copy(numerals + r, numerals + DIM(numerals),
+ std::ostream_iterator<char>(std::cout, " "));
+ std::cout << '\n';
} // PrintLetters
-
+char theMsg[] = "\nPlease select a function to test:\n\n"
+ "1. Next partial permutation\n"
+ "2. Previous partial permutation\n"
+ "3. Next partial combination\n"
+ "4. Previous partial combination\n"
+ "5. Next partial permutation with compare functor\n"
+ "6. Previous partial permutation with compare functor\n"
+ "7. Next partial combination with compare functor\n"
+ "8. Previous partial combination with compare functor\n"
+ "9. Quit\n"
+ "\nEnter the number of your selection: ";
// main -----------------------------------------------------------------//
int main(int argc, char** argv)
{
-#ifdef __MWERKS__
- argc = ccommand(&argv);
-#endif
-
unsigned r = argc < 2 ? 2 : lexical_cast<unsigned>(argv[1]);
- cout << "\nr is equal to " << r << ". Change on command line, e.g., "
+ std::cout << "\nr is equal to " << r << ". Change on command line, e.g., "
<< argv[0] << " 5\n\n";
- cout << "Please select a function to test:\n\n"
- << "1. Next r-permutation\n"
- << "2. Previous r-permutation\n"
- << "3. Next r-combination\n"
- << "4. Previous r-combination\n"
- << "5. Next r-permutation with compare functor\n"
- << "6. Previous r-permutation with compare functor\n"
- << "7. Next r-combination with compare functor\n"
- << "8. Previous r-combination with compare functor\n"
- << "9. Quit\n";
-
unsigned selection;
while(true)
{
- cout << "\nEnter the number of your selection: ";
- cin >> selection;
+ std::cout << theMsg;
+ std::cin >> selection;
- cout << "\nR-permutations and r-combinations appear to the left of the\n"
+ std::cout << "\nPartial permutations and partial combinations appear to the left of the\n"
<< "vertical bar.\n";
unsigned count = 1;
@@ -114,79 +104,88 @@
switch(selection)
{
case 1:
- cout << "\n\tNext r-permutations\n\n";
- partial_sort(numerals, numerals + r, numerals + DIM(numerals));
+ std::cout << "\n\tNext partial permutations\n\n";
+ std::partial_sort(numerals, numerals + r, numerals + DIM(numerals));
do {
- cout << setw(3) << count++ << ". ";
+ std::cout << std::setw(3) << count++ << ". ";
PrintLetters(r);
- } while(next_r_permutation(numerals, numerals + r, numerals + DIM(numerals)));
+ } while(next_partial_permutation(numerals, numerals + r, numerals + DIM(numerals)));
break;
case 2:
- cout << "\n\tPrevious r-permutations\n\n";
- partial_sort(numerals, numerals + r, numerals + DIM(numerals), greater<char>());
+ std::cout << "\n\tPrevious partial permutations\n\n";
+ std::partial_sort(numerals, numerals + r, numerals + DIM(numerals),
+ std::greater<char>());
do {
- cout << setw(3) << count++ << ". ";
+ std::cout << std::setw(3) << count++ << ". ";
PrintLetters(r);
- } while(prev_r_permutation(numerals, numerals + r, numerals + DIM(numerals)));
+ } while(prev_partial_permutation(numerals, numerals + r,
+ numerals + DIM(numerals)));
break;
case 3:
- cout << "\n\tNext r-combinations\n\n";
- partial_sort(numerals, numerals + r, numerals + DIM(numerals));
+ std::cout << "\n\tNext partial combinations\n\n";
+ std::partial_sort(numerals, numerals + r, numerals + DIM(numerals));
do {
- cout << setw(3) << count++ << ". ";
+ std::cout << std::setw(3) << count++ << ". ";
PrintLetters(r);
- } while(next_r_combination(numerals, numerals + r, numerals + DIM(numerals)));
+ } while(next_partial_combination(numerals, numerals + r, numerals + DIM(numerals)));
break;
case 4:
- cout << "\n\tPrevious r-combinations\n\n";
- sort(numerals, numerals + DIM(numerals));
- rotate(numerals, numerals + DIM(numerals) - r, numerals + DIM(numerals));
+ std::cout << "\n\tPrevious partial combinations\n\n";
+ std::sort(numerals, numerals + DIM(numerals));
+ std::rotate(numerals, numerals + DIM(numerals) - r, numerals + DIM(numerals));
do {
- cout << setw(3) << count++ << ". ";
+ std::cout << std::setw(3) << count++ << ". ";
PrintLetters(r);
- } while(prev_r_combination(numerals, numerals + r, numerals + DIM(numerals)));
+ } while(prev_partial_combination(numerals, numerals + r, numerals + DIM(numerals)));
break;
case 5:
- cout << "\n\tNext r-permutations using compare functor\n\n";
- partial_sort(numerals, numerals + r, numerals + DIM(numerals), greater<char>());
+ std::cout << "\n\tNext partial permutations using compare functor\n\n";
+ std::partial_sort(numerals, numerals + r, numerals + DIM(numerals),
+ std::greater<char>());
do {
- cout << setw(3) << count++ << ". ";
+ std::cout << std::setw(3) << count++ << ". ";
PrintLetters(r);
- } while(next_r_permutation(numerals, numerals + r, numerals + DIM(numerals), greater<char>()));
+ } while(next_partial_permutation(numerals, numerals + r,
+ numerals + DIM(numerals), std::greater<char>()));
break;
case 6:
- cout << "\n\tPrevious r-permutations using compare functor\n\n";
- partial_sort(numerals, numerals + r, numerals + DIM(numerals));
+ std::cout << "\n\tPrevious partial permutations using compare functor\n\n";
+ std::partial_sort(numerals, numerals + r, numerals + DIM(numerals));
do {
- cout << setw(3) << count++ << ". ";
+ std::cout << std::setw(3) << count++ << ". ";
PrintLetters(r);
- } while(prev_r_permutation(numerals, numerals + r, numerals + DIM(numerals), greater<char>()));
+ } while(prev_partial_permutation(numerals, numerals + r,
+ numerals + DIM(numerals), std::greater<char>()));
break;
case 7:
- cout << "\n\tNext r-combinations using compare functor\n\n";
- partial_sort(numerals, numerals + r, numerals + DIM(numerals), greater<char>());
+ std::cout << "\n\tNext partial combinations using compare functor\n\n";
+ std::partial_sort(numerals, numerals + r, numerals + DIM(numerals),
+ std::greater<char>());
do {
- cout << setw(3) << count++ << ". ";
+ std::cout << std::setw(3) << count++ << ". ";
PrintLetters(r);
- } while(next_r_combination(numerals, numerals + r, numerals + DIM(numerals), greater<char>()));
+ } while(next_partial_combination(numerals, numerals + r,
+ numerals + DIM(numerals), std::greater<char>()));
break;
case 8:
- cout << "\n\tPrevious r-combinations using compare functor\n\n";
- sort(numerals, numerals + DIM(numerals), greater<char>());
- rotate(numerals, numerals + DIM(numerals) - r, numerals + DIM(numerals));
+ std::cout << "\n\tPrevious partial combinations using compare functor\n\n";
+ std::sort(numerals, numerals + DIM(numerals), std::greater<char>());
+ std::rotate(numerals, numerals + DIM(numerals) - r,
+ numerals + DIM(numerals));
do {
- cout << setw(3) << count++ << ". ";
+ std::cout << std::setw(3) << count++ << ". ";
PrintLetters(r);
- } while(prev_r_combination(numerals, numerals + r, numerals + DIM(numerals), greater<char>()));
+ } while(prev_partial_combination(numerals, numerals + r,
+ numerals + DIM(numerals), std::greater<char>()));
break;
case 9:
default:
- cout << "\nAll done!" << endl;
+ std::cout << "\nAll done!" << std::endl;
return EXIT_SUCCESS;
} // switch
// Print numerals again to verify that last function call resets string.
- cout << " 1. ";
+ std::cout << " 1. ";
PrintLetters(r);
} // while
Modified: sandbox/libs/sequence_algo/example/combinatorial_ex2.cpp
==============================================================================
--- sandbox/libs/sequence_algo/example/combinatorial_ex2.cpp (original)
+++ sandbox/libs/sequence_algo/example/combinatorial_ex2.cpp 2008-01-12 14:48:11 EST (Sat, 12 Jan 2008)
@@ -1,6 +1,6 @@
// combinatorial_ex2.cpp - Ask Marilyn Puzzle, Parade magazine 5/5/02 --------------//
-// Copyright © Philip F. Garofalo 2002. All rights reserved.
+// Copyright © Philip F. Garofalo 2008. All rights reserved.
// Permission to copy, use, modify, sell and distribute this software
// is granted provided this copyright notice appears in all copies.
// This software is provided "as is" without express or implied
@@ -36,18 +36,15 @@
#include <string>
#include <exception>
#include <stdexcept>
-
+#include <set>
+#include <sstream>
#include <cstdlib>
#include <cassert>
-using namespace std;
-#include "combinatorial.hpp" // next_r_permutation()
+#include "combinatorial.hpp" // next_partial_permutation()
#define DIM(a) (sizeof(a)/sizeof(a)[0])
-const char filename[] = "lexicon.txt";
-vector<string> theDictionary;
-
const char tri[12][4] = {
"ate",
"con",
@@ -63,12 +60,12 @@
"tic"
};
#if !defined _MSC_VER
-vector<string> theSegs(tri, &tri[12]);
+std::vector<string> theSegs(tri, &tri[12]);
#else
// I couldn't assuage MSC about the pointer parameters in the above
// definition so, I'll define it with the default constructor here
// and initialize it in main().
-vector<string> theSegs;
+std::vector<std::string> theSegs;
#endif
const int R = 4; // select 4 three-letter words at a time
@@ -79,7 +76,7 @@
// partial template specialization, so we'll need to explicitly specialize
// iterator_traits for the container type, which is string* in this example
// application. It is required only before the call to the default version
-// of prev_r_permutation,the one without the user-supplied compare function.
+// of prev_partial_permutation,the one without the user-supplied compare function.
namespace std {
template<>
@@ -94,6 +91,47 @@
#endif // MSC_VER
+//----------------------------
+
+class Dictionary
+{
+ std::set<std::string> itsDictionary;
+public:
+ Dictionary(const char* filename);
+ bool LookUp(const std::string& word) const;
+}; // Dictionary
+
+Dictionary::Dictionary(const char* filename)
+{
+ std::ifstream ifs(filename);
+ if (!ifs)
+ {
+ std::ostringstream os;
+ os << "Couldn't open " << filename << std::ends;
+ throw os.str();
+ }
+
+ // Loading the dictionary will use up a lot of memory here. MacOS
+ // developers make sure to set the application's minimum memory
+ // requirement to at least 1 MB.
+ std::cout << "\nReading the dictionary file " << filename << " ..." << std::flush;
+
+ // Copy words from dictionary file to a vector:
+ typedef std::istream_iterator<std::string> string_input;
+ copy(string_input(ifs), string_input(), inserter(itsDictionary, itsDictionary.end()));
+ ifs.close();
+ std::cout << "\nThe dictionary contains " << itsDictionary.size() << " words.\n\n";
+
+} // Dictionary ctor
+
+inline bool Dictionary::LookUp(const std::string& word) const
+{
+ return itsDictionary.find(word) != itsDictionary.end();
+} // Dictionary::LookUp
+
+
+Dictionary theDictionary("..\\lexicon.txt");
+
// WordSearch -----------------------------------------------------------//
// This function prints out the current set of 3-letter word segments
@@ -103,20 +141,21 @@
void WordSearch()
{
// sort to start the permutation series
- partial_sort(theSegs.begin(), theSegs.begin() + R, theSegs.end());
+ std::partial_sort(theSegs.begin(), theSegs.begin() + R, theSegs.end());
// display the initial set of 3-letter word segments
- copy(theSegs.begin(), theSegs.end(), ostream_iterator<string>(cout, "\t"));
- cout << '\n';
+ std::copy(theSegs.begin(), theSegs.end(),
+ std::ostream_iterator<std::string>(std::cout, "\t"));
+ std::cout << '\n';
do {
- string trial_word = theSegs[0] + theSegs[1] + theSegs[2] + theSegs[3];
- if (binary_search(theDictionary.begin(), theDictionary.end(), trial_word))
+ std::string trial_word = theSegs[0] + theSegs[1] + theSegs[2] + theSegs[3];
+ if (theDictionary.LookUp(trial_word))
{
- cout << trial_word << '\n';
+ std::cout << trial_word << '\n';
break;
} // if
- } while(boost::next_r_permutation(theSegs.begin(), theSegs.begin() + R,
+ } while(boost::next_partial_permutation(theSegs.begin(), theSegs.begin() + R,
theSegs.end()));
// Delete the segments for the found word.
@@ -128,7 +167,7 @@
// Solves the "Ask Marilyn" puzzle in two ways. The first is simple
// but somewhat inefficient. It was my initial attempt at solving the
-// problem using next_r_permutation. It goes through the series of 4-
+// problem using next_partial_permutation. It goes through the series of 4-
// permutations of the 12 segments until it finds the three 12-letter
// words. Assuming that the words are evenly spaced through the permutation
// series then the last word will be 3/4 of the way through
@@ -147,9 +186,9 @@
int main()
{
- cout << "From \"Ask Marilyn\", Parade magazine 5/5/02\n\n";
+ std::cout << "From \"Ask Marilyn\", Parade magazine 5/5/02\n\n";
- cout << "Dear Marilyn,\n\
+ std::cout << "Dear Marilyn,\n\
Can you combine these 12 three-letter words to form three 12-letter words\n\
instead? (Example: car + tog + rap + her = cartographer.)\n\
\
@@ -160,57 +199,36 @@
#if defined _MSC_VER
// See comment above on the definition of theSegs vector.
- copy(&tri[0], &tri[DIM(tri)], back_inserter(theSegs));
+ std::copy(&tri[0], &tri[DIM(tri)], back_inserter(theSegs));
#endif
- // open the dictionary
-
- ifstream ifs(filename);
- if (!ifs)
- {
- cerr << "Couldn't open " << filename << endl;
- return EXIT_FAILURE;
- }
-
- // Copy words from dictionary file to a vector:
- typedef istream_iterator<string> string_input;
-
- cout << "\nReading the dictionary file " << filename << " ..." << flush;
-
- // Loading the dictionary will use up a lot of memory here. MacOS
- // developers make sure to set the application's minimum memory
- // requirement to at least 1 MB.
- copy(string_input(ifs), string_input(), back_inserter(theDictionary));
-
- cout << "\nThe dictionary contains " << theDictionary.size() << " words.\n\n";
-
// First method; search the dictionary for every permutation. Stop after
// the third word is found.
- cout << "\n\n--- First lookup method ---\n\n";
+ std::cout << "\n\n--- First lookup method ---\n\n";
// No need for an initial sort; theSegs is already sorted.
int count = 0;
do {
- string trial_word = theSegs[0] + theSegs[1] + theSegs[2] + theSegs[3];
- if (binary_search(theDictionary.begin(), theDictionary.end(), trial_word))
+ std::string trial_word = theSegs[0] + theSegs[1] + theSegs[2] + theSegs[3];
+ if (theDictionary.LookUp(trial_word))
{
- cout << ++count << ". " << trial_word << '\n';
+ std::cout << ++count << ". " << trial_word << '\n';
}
} while(count < 3 &&
- boost::next_r_permutation(theSegs.begin(), theSegs.begin() + R,
+ boost::next_partial_permutation(theSegs.begin(), theSegs.begin() + R,
theSegs.end()));
// Second method; progressively reduce the permutation set by four after
// each word is found to reduce the number of permutations to search,.
- cout << "\n\n--- More efficient way to solve the same problem ---\n\n";
+ std::cout << "\n\n--- More efficient way to solve the same problem ---\n\n";
WordSearch(); // find first word
WordSearch(); // find second word
WordSearch(); // find third and last word
- cout << "\n\nAll done!" << endl;
+ std::cout << "\n\nAll done!" << std::endl;
return EXIT_SUCCESS;
} // main