Boost-Commit :

Date view	Thread view	Subject view	Author view

From: philgarofalo_at_[hidden]
Date: 2008-01-01 14:42:36

Next message: daniel_james_at_[hidden]: "[Boost-commit] svn:boost r42402 - branches/unordered/trunk"
Previous message: philgarofalo_at_[hidden]: "[Boost-commit] svn:boost r42400 - sandbox/boost/sequence_algo"

Author: pgarofalo
Date: 2008-01-01 14:42:35 EST (Tue, 01 Jan 2008)
New Revision: 42401
URL: http://svn.boost.org/trac/boost/changeset/42401

Log:
Changed the _r_ in the function names to _partial_, GACAP style. Also renamed function parameter r to middle.
Text files modified:
sandbox/libs/sequence_algo/doc/combinatorial.html | 206 ++++++++++++++++++++++++++++++++-------
1 files changed, 168 insertions(+), 38 deletions(-)

Modified: sandbox/libs/sequence_algo/doc/combinatorial.html
==============================================================================
--- sandbox/libs/sequence_algo/doc/combinatorial.html (original)
+++ sandbox/libs/sequence_algo/doc/combinatorial.html 2008-01-01 14:42:35 EST (Tue, 01 Jan 2008)
@@ -2,49 +2,80 @@
<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>
 <a href="#Introduction">Introduction</a>
 </li>
+
+
 <li>
 <a href="#Description">Description</a>
 </li>
+
+
 <li>
 <a href="#Performance">Performance</a>
 </li>
+
+
 <li>
 <a href="#Examples">Examples and Test Programs</a>
 </li>
+
+
 <li>
 <a href="#References">References</a>
 </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
@@ -53,43 +84,67 @@
permutations. For this reason, I've written a suite of generic combinatorial
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.
+referred to as r-permutations and r-combinations, respectively, in some texts.
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>

+
+

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>
 <a href="#next_r_permutation">next_partial_permutation</a>,
 </li>
+
+
 <li>
 <a href="#prev_r_permutation">prev_partial_permutation</a>,
 </li>
+
+
 <li>
 <a href="#next_r_combination">next_partial_combination</a>,
 </li>
+
+
 <li>
 <a href="#prev_r_combination">prev_partial_combination</a>,
 </li>
+
+
 <li>
 and user-supplied binary comparison predicate versions of each.
 </li>
+
+
</ul>

+
+

They're defined in the header file conbinatorial.hpp in
the directory boost/sequence_algo. They are members of the boost namespace.
@@ -97,137 +152,178 @@
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_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
+the elements in [first, middle), from the larger range [first, last) where first
+< middle <= last, such that they represent the next r-permutation of elements
in lexicographical order. When calling the function for the first time, the
elements in [first, last) must be in ascending lexicographical order. Typically,
when the function is called it arranges the next r-permutation in [first,
-r) and returns true. When the last permutation in lexicographical order is
+middle) 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_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>
+
+
+<pre>template<class RandomAccessIterator> bool next_partial_permutation(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last) template<class RandomAccessIterator, class Compare> bool next_partial_permutation(RandomAccessIterator first, RandomAccessIterator middle, 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
+the elements in [first, middle), from the larger range [first, last) where first
+< middle <= last, such that they represent the previous r-permutation of
elements in lexicographical order. When calling the function for the first
time, the elements in [first, last) must be in descending lexicographical
order. Typically, when the function is called it arranges the previous
-r-permutation in [first, r) and returns true. When the first permutation
+r-permutation in [first, middle) and returns true. When the first permutation
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_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>
+
+
+<pre>template<class RandomAccessIterator> bool prev_partial_permutation(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last) template<class RandomAccessIterator, class Compare> bool prev_partial_permutation(RandomAccessIterator first, RandomAccessIterator middle, 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
+the elements in [first, middle), from the larger range [first, last) where first
+< middle <= last, such that they represent the next r-combination of elements
in lexicographical order. The elements in [first, last) must be in ascending
lexicographical order. When the function is called and a next combination
-exists, it arranges the next r-combination in [first, r) and returns true.
+exists, it arranges the next r-combination in [first, middle) and returns true.
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_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>
+
+
+<pre>template<class RandomAccessIterator> bool next_partial_combination(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last) template<class RandomAccessIterator, class Compare> bool next_partial_combination(RandomAccessIterator first, RandomAccessIterator middle, 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
+the elements in [first, middle), from the larger range [first, last) where first
+< middle <= last, such that they represent the previous r-combination of
elements in lexicographical order. The elements in [first, last) must be
in ascending lexicographical order. When the function is called and a prior
-combination exists, it arranges the previous r-combination in [first, r)
+combination exists, it arranges the previous r-combination in [first, middle)
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_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>
+
+
+<pre>template<class RandomAccessIterator> bool prev_partial_combination(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last) template<class RandomAccessIterator, class Compare> bool prev_partial_combination(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp) </pre>
+
+

<h4>
 -- Support Functions --
</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
-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
-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>
+<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>

-<h3>
- <a name="Performance">Performance</a>
+
+
+
+min_element_if - returns the smallest element, for the order comp, of the subsequence of [first,last) satisfying the predicate (or last if none
+<pre>template <class ForwardIter, class UnaryPredicate> ForwardIter min_element_if(ForwardIter first, ForwardIter last, UnaryPredicate cond); template <class ForwardIter, class BinaryPredicate, class UnaryPredicate> ForwardIter min_element_if(ForwardIter first, ForwardIter last, BinaryPredicate comp, UnaryPredicate cond);   </pre>
+max_element_if - returns the largest element of the subsequence of [first,last) satisfying the predicate (or last if none).
+<pre>template <class ForwardIter, class UnaryPredicate> ForwardIter max_element_if(ForwardIter first, ForwardIter last, UnaryPredicate cond); template <class ForwardIter, class BinaryPredicate, class UnaryPredicate> ForwardIter max_element_if(ForwardIter first, ForwardIter last, BinaryPredicate comp, UnaryPredicate cond) </pre>
+<h3><a name="Performance">Performance</a>
</h3>

+
+

-Each permutation or combination function performs (r - first)/2 swaps on
+Each permutation or combination function performs (middle - first)/2 swaps on
average. (To be verified.)

+
+
<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
+The following programs include boost/sequence_algo/combinatorial.hpp, headers
+from the C++ standard library, and Boost. These folders must be in your
compiler include paths.

+
+


+
+
<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.
 </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_partial_permutation. It reads in the
 dictionary file lexicon.txt. You'll the files in the libs/sequence_algo/example
 subdirectory.
 </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
@@ -239,59 +335,93 @@
 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.
 </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>
+
+
 <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>
+
+
 <li>
 Sedgewick, Robert. <cite>Algorithms</cite>. 2nd ed. Reading, MA: Addison-Wesley,
 1988.
 </li>
+
+
 <li>
 Stepanov, Alexander and Meng Lee. <cite>The Standard Template Library</cite>.
 Palo Alto: Hewlett-Packard, 1995.
 </li>
+
+
 <li>
 Stroustrup, Bjarne. <cite>The C++ Programming Language</cite>. Special ed.
- Reading, MA: Addison-Wesley-AT&T, 2000.
- </li>
+ Reading, MA: Addison-Wesley-AT&T, 2000.</li>
+ <li>Sedgewick, Robert. "Permutation Generation Methods". Association for Computing Machinery, Inc., 1977</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>

Next message: daniel_james_at_[hidden]: "[Boost-commit] svn:boost r42402 - branches/unordered/trunk"
Previous message: philgarofalo_at_[hidden]: "[Boost-commit] svn:boost r42400 - 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