Boost-Commit :

Date view	Thread view	Subject view	Author view

From: philgarofalo_at_[hidden]
Date: 2007-12-31 23:13:23

Next message: philgarofalo_at_[hidden]: "[Boost-commit] svn:boost r42399 - sandbox/boost/sequence_algo"
Previous message: philgarofalo_at_[hidden]: "[Boost-commit] svn:boost r42397 - sandbox/boost/sequence_algo"

Author: pgarofalo
Date: 2007-12-31 23:13:23 EST (Mon, 31 Dec 2007)
New Revision: 42398
URL: http://svn.boost.org/trac/boost/changeset/42398

Log:
Changed the _r_ in the function names to _partial_, GACAP style.
Text files modified:
sandbox/libs/sequence_algo/doc/combinatorial.html | 393 ++++++++++++++++++++-------------------
1 files changed, 202 insertions(+), 191 deletions(-)

Modified: sandbox/libs/sequence_algo/doc/combinatorial.html
==============================================================================
--- sandbox/libs/sequence_algo/doc/combinatorial.html (original)
+++ sandbox/libs/sequence_algo/doc/combinatorial.html 2007-12-31 23:13:23 EST (Mon, 31 Dec 2007)
@@ -1,33 +1,51 @@
-<HTML>
-<HEAD>
- <TITLE>Generic Combinatorial Algorithms</TITLE>
-</HEAD>
-<BODY bgcolor="#ffffff" text="#000000">
-<H1>
- <CENTER>
- next_r_permutation, prev_r_permutation, next_r_combination, prev_r_combination
- </CENTER>
-</H1>
-<H3>
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html lang="en-us">
+<head>
+
+
+ <title>Generic Combinatorial Algorithms</title>
+</head>
+
+<body style="direction: ltr;" bgcolor="#ffffff" text="#000000">
+
+<h1>
+
+<center>
+ next_partial_permutation, prev_partial_permutation, next_partial_combination, prev_partial_combination
+ </center>
+
+</h1>
+
+<h3>
 Contents
-</H3>
-<UL>
- <LI>
- Introduction
- <LI>
- Description
- <LI>
- Performance
- <LI>
- Examples and Test Programs
- <LI>
- References
-</UL>
-
-<H3>
- <A name="Introduction">Introduction</A>
-</H3>
-
+</h3>
+
+<ul>
+
+ <li>
+ Introduction
+ </li>
+ <li>
+ Description
+ </li>
+ <li>
+ Performance
+ </li>
+ <li>
+ Examples and Test Programs
+ </li>
+ <li>
+ References
+ </li>
+</ul>
+
+
+
+<h3>
+ <a name="Introduction">Introduction</a>
+</h3>
+
+
A common problem in discrete mathematics is the need to generate all the
permutations or combinations of a subset of objects from a larger set of
objects. The STL's permutation algorithms, next_permutation and prev_permutation,
@@ -36,48 +54,64 @@
algorithms to complement the existing functions. Specifically, they are
algorithms to implement ordered and unordered selection without replacement,
referred to as r-permutations and r-combinations, respectively, in many texts.
-For instance, see [1].
-
+For instance, see [1].
+
+
The programs have been compiled and tested on MacOS 9 using Metrowerks
Codewarrior version 5 and on Windows 98 using Microsoft Visual C++ version
6.0.
-
-<H3>
- <A name="Description">Description</A>
-</H3>
-
+
+
+
+<h3>
+ <a name="Description">Description</a>
+</h3>
+
+
There are eight primary functions in this collection and they follow the
format and semantics commonly found among functions in the STL. They are
-<UL>
- <LI>
- next_r_permutation,
- <LI>
- prev_r_permutation,
- <LI>
- next_r_combination,
- <LI>
- prev_r_combination,
- <LI>
+
+<ul>
+
+ <li>
+ next_partial_permutation,
+ </li>
+ <li>
+ prev_partial_permutation,
+ </li>
+ <li>
+ next_partial_combination,
+ </li>
+ <li>
+ prev_partial_combination,
+ </li>
+ <li>
 and user-supplied binary comparison predicate versions of each.
-</UL>
-
-They're defined in the header file conbinatorial.hpp in
+ </li>
+</ul>
+
+
+They're defined in the header file conbinatorial.hpp in
the directory boost/sequence_algo. They are members of the boost namespace.
The file itself uses a function from the boost library, so make sure that
the Boost directory is in your header include path. See the example programs
listed in the section below.
-
+
+
Items in input sequences must either work with the built-in less than (<)
operator, have a less than operator defined, or have a user-defined binary
comparison operation provided at the point of call.
-
+
+
Like the STL's permutation algorithms, objects in the input sequence to these
functions should be in lexicographical order (based on the less than operator,
unless a binary comparison function is supplied) on the first call.
-
-The input must define a strict weak ordering [3].
-
-<A name="next_r_permutation">next_r_permutation</A> - arranges
+
+
+The input must define a strict weak ordering [3].
+
+
+<a name="next_r_permutation">next_partial_permutation</a> - arranges
the elements in [first, r), from the larger range [first, last) where first
< r <= last, such that they represent the next r-permutation of elements
in lexicographical order. When calling the function for the first time, the
@@ -86,19 +120,11 @@
r) and returns true. When the last permutation in lexicographical order is
passed in, the function sorts the entire range, [first, last) into ascending
order, restarting the sequence, and returns false.
-<PRE>
-template<class RandomAccessIterator>
-bool
-next_r_permutation(RandomAccessIterator first, RandomAccessIterator r,
- RandomAccessIterator last)
-
-template<class RandomAccessIterator, class Compare>
-bool
-next_r_permutation(RandomAccessIterator first, RandomAccessIterator r,
- RandomAccessIterator last, Compare comp)
-</PRE>
-
-<A name="prev_r_permutation">prev_r_permutation</A> - arranges
+
+<pre>template<class RandomAccessIterator> bool next_partial_permutation(RandomAccessIterator first, RandomAccessIterator r, RandomAccessIterator last) template<class RandomAccessIterator, class Compare> bool next_partial_permutation(RandomAccessIterator first, RandomAccessIterator r, RandomAccessIterator last, Compare comp) </pre>
+
+
+<a name="prev_r_permutation">prev_partial_permutation</a> - arranges
the elements in [first, r), from the larger range [first, last) where first
< r <= last, such that they represent the previous r-permutation of
elements in lexicographical order. When calling the function for the first
@@ -108,19 +134,11 @@
in lexicographical order is passed in, the function sorts the entire range,
[first, last) into descending order, restarting the sequence at the end,
and returns false.
-<PRE>
-template<class RandomAccessIterator>
-bool
-prev_r_permutation(RandomAccessIterator first, RandomAccessIterator r,
- RandomAccessIterator last)
-
-template<class RandomAccessIterator, class Compare>
-bool
-prev_r_permutation(RandomAccessIterator first, RandomAccessIterator r,
- RandomAccessIterator last, Compare comp)
-</PRE>
-
-<A name="next_r_combination">next_r_combination</A> - arranges
+
+<pre>template<class RandomAccessIterator> bool prev_partial_permutation(RandomAccessIterator first, RandomAccessIterator r, RandomAccessIterator last) template<class RandomAccessIterator, class Compare> bool prev_partial_permutation(RandomAccessIterator first, RandomAccessIterator r, RandomAccessIterator last, Compare comp) </pre>
+
+
+<a name="next_r_combination">next_partial_combination</a> - arranges
the elements in [first, r), from the larger range [first, last) where first
< r <= last, such that they represent the next r-combination of elements
in lexicographical order. The elements in [first, last) must be in ascending
@@ -129,19 +147,11 @@
If the next combination does not exist, the function sorts the entire range,
[first, last) into ascending order, thus restarting the sequence, and returns
false.
-<PRE>
-template<class RandomAccessIterator>
-bool
-next_r_combination(RandomAccessIterator first, RandomAccessIterator r,
- RandomAccessIterator last)
-
-template<class RandomAccessIterator, class Compare>
-bool
-next_r_combination(RandomAccessIterator first, RandomAccessIterator r,
- RandomAccessIterator last, Compare comp)
-</PRE>
-
-<A name="prev_r_combination">prev_r_combination</A> - arranges
+
+<pre>template<class RandomAccessIterator> bool next_partial_combination(RandomAccessIterator first, RandomAccessIterator r, RandomAccessIterator last) template<class RandomAccessIterator, class Compare> bool next_partial_combination(RandomAccessIterator first, RandomAccessIterator r, RandomAccessIterator last, Compare comp) </pre>
+
+
+<a name="prev_r_combination">prev_partial_combination</a> - arranges
the elements in [first, r), from the larger range [first, last) where first
< r <= last, such that they represent the previous r-combination of
elements in lexicographical order. The elements in [first, last) must be
@@ -150,92 +160,75 @@
and returns true. If the prior combination does not exist, the function arranges
the sequence [first, last) into the last r-combination, thus restarting the
sequence at the end, and returns false.
-<PRE>
-template<class RandomAccessIterator>
-bool
-prev_r_combination(RandomAccessIterator first, RandomAccessIterator r,
- RandomAccessIterator last)
-
-template<class RandomAccessIterator, class Compare>
-bool
-prev_r_combination(RandomAccessIterator first, RandomAccessIterator r,
- RandomAccessIterator last, Compare comp)
-</PRE>
-<H4>
+
+<pre>template<class RandomAccessIterator> bool prev_partial_combination(RandomAccessIterator first, RandomAccessIterator r, RandomAccessIterator last) template<class RandomAccessIterator, class Compare> bool prev_partial_combination(RandomAccessIterator first, RandomAccessIterator r, RandomAccessIterator last, Compare comp) </pre>
+
+<h4>
 -- Support Functions --
-</H4>
-
-is_sorted - returns true if [first, last) is in sorted order,
+</h4>
+
+
+is_sorted - returns true if [first, last) is in sorted order,
based on the less than operator or the compare operator.
-<PRE>
-template<class ForwardIterator>
-bool
-is_sorted(ForwardIterator first, ForwardIterator last)
-
-template<class ForwardIterator, class Compare>
-bool
-is_sorted(ForwardIterator first, ForwardIterator last, Compare comp)
-</PRE>
-
-min_element_greater_than - returns an iterator pointing
+
+<pre>template<class ForwardIterator> bool is_sorted(ForwardIterator first, ForwardIterator last) template<class ForwardIterator, class Compare> bool is_sorted(ForwardIterator first, ForwardIterator last, Compare comp) </pre>
+
+
+min_element_greater_than - returns an iterator pointing
to the smallest value in [first, last) greater than x. last is returned if
value is not found. Time complexity is linear, O((last-first)/2) assignments
in average case.
-<PRE>
-template<class ForwardIterator, class T>
-ForwardIterator
-min_element_greater_than(ForwardIterator first, ForwardIterator last,
- const T& x)
-
-template<class ForwardIterator, class T, class Compare>
-ForwardIterator
-min_element_greater_than(ForwardIterator first, ForwardIterator last,
- const T& x, Compare comp)
-</PRE>
-
-max_element_less_than - returns an iterator pointing to
+
+<pre>template<class ForwardIterator, class T> ForwardIterator min_element_greater_than(ForwardIterator first, ForwardIterator last, const T& x) template<class ForwardIterator, class T, class Compare> ForwardIterator min_element_greater_than(ForwardIterator first, ForwardIterator last, const T& x, Compare comp) </pre>
+
+
+max_element_less_than - returns an iterator pointing to
the largest object in [first, last) less than x. last is returned if the
object doesn't exist.
-<PRE>
-template<class ForwardIterator, class T>
-ForwardIterator
-max_element_less_than(ForwardIterator first, ForwardIterator last, const T& x)
-
-template<class ForwardIterator, class T, class Compare>
-ForwardIterator
-max_element_less_than(ForwardIterator first, ForwardIterator last,
- const T& x, Compare comp)
-</PRE>
-<H3>
- <A name="Performance">Performance</A>
-</H3>
-
+
+<pre>template<class ForwardIterator, class T> ForwardIterator max_element_less_than(ForwardIterator first, ForwardIterator last, const T& x) template<class ForwardIterator, class T, class Compare> ForwardIterator max_element_less_than(ForwardIterator first, ForwardIterator last, const T& x, Compare comp) </pre>
+
+<h3>
+ <a name="Performance">Performance</a>
+</h3>
+
+
Each permutation or combination function performs (r - first)/2 swaps on
average. (To be verified.)
-<H3>
- <A name="Examples">Examples and Test Programs</A>
-</H3>
-
+
+<h3>
+ <a name="Examples">Examples and Test Programs</a>
+</h3>
+
+
The following programs include boost/sequence_algo/conbinatorial.hpp, headers
from the C++ standard library, and Boost. Make sure these files are in your
compiler include paths.
-
-<DL>
- <DT>
- combinatorial_ex1.cpp
- <DD>
+
+
+
+<dl>
+
+ <dt>
+ combinatorial_ex1.cpp
+ </dt>
+ <dd>
 This is interactive console I/O program presents a menu that lets you run
 each function individually. It is in the libs/sequence_algo/example subdirectory.
- <DT>
- combinatorial_ex2.cpp
- <DD>
+ </dd>
+ <dt>
+ combinatorial_ex2.cpp
+ </dt>
+ <dd>
 This console I/O program solves a puzzle from a recent "Ask Marilyn" column
- in <CITE>Parade</CITE> magazine using next_r_permutation. It reads in the
+ in <cite>Parade</cite> magazine using next_partial_permutation. It reads in the
 dictionary file lexicon.txt. You'll the files in the libs/sequence_algo/example
 subdirectory.
- <DT>
- test_combinatorial.cpp
- <DD>
+ </dd>
+ <dt>
+ test_combinatorial.cpp
+ </dt>
+ <dd>
 This program uses the Boost Unit Test framework for error reporting and is
 compatible with the Boost regression test program. It is a modification and
 elaboration of combinatorial_ex1.cpp. The interactive functionality has been
@@ -245,42 +238,60 @@
 basis path, boundary, and condition testing. Test_combinatorial.cpp sits
 in the libs/sequence_algo/test subdirectory. To build this program, it is
 necessary to link to cpp_main.cpp and test_main.cpp in boost/test.
- <DT>
-</DL>
-<H3>
- <A name="References">References</A>
-</H3>
-
-<OL>
- <LI>
- <A name="Johnsonbaugh">Johnsonbaugh</A>, Richard. <CITE>Discrete
- Mathematics</CITE>. 2nd ed. New York: Macmillan, 1990.
- <LI>
- Lippman, Stanley B. and Josée Lajoie. <CITE>C++ Primer</CITE>. 3rd
+ </dd>
+ <dt>
+ </dt>
+</dl>
+
+<h3>
+ <a name="References">References</a>
+</h3>
+
+
+
+<ol>
+
+ <li>
+ <a name="Johnsonbaugh">Johnsonbaugh</a>, Richard. <cite>Discrete
+ Mathematics</cite>. 2nd ed. New York: Macmillan, 1990.
+ </li>
+ <li>
+ Lippman, Stanley B. and Josée Lajoie. <cite>C++ Primer</cite>. 3rd
 ed. Reading, MA: Addison-Wesley-AT&T, 1998.
- <LI>
- <A name="Musser">Musser</A>, David R. and Atul Saini. <CITE>STL Tutorial
- and Reference Guide: C++ Programming with the Standard Template Library</CITE>.
+ </li>
+ <li>
+ <a name="Musser">Musser</a>, David R. and Atul Saini. <cite>STL Tutorial
+ and Reference Guide: C++ Programming with the Standard Template Library</cite>.
 Reading, MA: Addison-Wesley-Modena Software, 1996.
- <LI>
- Sedgewick, Robert. <CITE>Algorithms</CITE>. 2nd ed. Reading, MA: Addison-Wesley,
+ </li>
+ <li>
+ Sedgewick, Robert. <cite>Algorithms</cite>. 2nd ed. Reading, MA: Addison-Wesley,
 1988.
- <LI>
- Stepanov, Alexander and Meng Lee. <CITE>The Standard Template Library</CITE>.
+ </li>
+ <li>
+ Stepanov, Alexander and Meng Lee. <cite>The Standard Template Library</cite>.
 Palo Alto: Hewlett-Packard, 1995.
- <LI>
- Stroustrup, Bjarne. <CITE>The C++ Programming Language</CITE>. Special ed.
+ </li>
+ <li>
+ Stroustrup, Bjarne. <cite>The C++ Programming Language</cite>. Special ed.
 Reading, MA: Addison-Wesley-AT&T, 2000.
-</OL>
-
- <HR size="2" width="100%">
-
+ </li>
+</ol>
+
+
+ 
+<hr size="2" width="100%">
+
Copyright © Philip F. Garofalo 2002. 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 warranty, and with no claim as to its
suitability for any purpose.
-
+
+
Updated on June 20, 2002
-</BODY></HTML>
+
+</body>
+</html>

Next message: philgarofalo_at_[hidden]: "[Boost-commit] svn:boost r42399 - sandbox/boost/sequence_algo"
Previous message: philgarofalo_at_[hidden]: "[Boost-commit] svn:boost r42397 - sandbox/boost/sequence_algo"

Date view	Thread view	Subject view	Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk