possible bug with STL prev_permutation in VC++7.1 professional

possible bug with STL prev_permutation in VC++7.1 professional

Post by Cheng_Wu_C » Thu, 04 Mar 2004 14:27:50


his is a multipart message in MIME format.
Hi gurus,

I think this is a bug for prev_permutation because this behavior is not
observed with next_permutation. The code (modification from MSDN example)
below will go into infinite loop. Check it out and let me know what do
you think.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>

using namespace std ;

void main()
{
const int VECTOR_SIZE = 4;

// Define a template class vector of strings
typedef vector<string> StrVector;

// Define an iterator for template class vector of strings
typedef StrVector::iterator StrVectorIt;

// Define an ostream iterator for strings
typedef ostream_iterator<string>
StrOstreamIt;

StrVector Pattern(VECTOR_SIZE);

StrVectorIt start, end, it;

StrOstreamIt outIt(cout, " ");

// location of first element of Pattern
start = Pattern.begin();

// one past the location last element of Pattern
end = Pattern.end();

//Initialize vector Pattern
Pattern[0] = "B";
Pattern[1] = "A";
Pattern[2] = "C";
Pattern[3] = "A";

// print content of Pattern
cout << "Before calling prev_permutation..." << endl << "Pattern: [";
for (it = start; it != end; it++)
cout << " " << *it;
cout << " ]" << endl;

// Generate all possible permutations
cout << "After calling prev_permutation...." << endl;
while ( prev_permutation(start, end, less <string>()) )
{
cout << "[ ";
copy(start, end, outIt);
cout << "]" << endl;
}
}

With regards,
Cheng Wu


<br><font size=2 face="sans-serif">Hi gurus,</font>
<br>
<br><font size=2 face="sans-serif">I think this is a bug for prev_permutation
because this behavior is not observed with next_permutation.  The
code (modification from MSDN example)  below will go into infinite
loop.  Check it out and let me know what do you think.</font>
<br>
<br><font size=2 face="sans-serif">#include <iostream></font>
<br><font size=2 face="sans-serif">#include <vector></font>
<br><font size=2 face="sans-serif">#include <string></font>
<br><font size=2 face="sans-serif">#include <algorithm></font>
<br><font size=2 face="sans-serif">#include <functional></font>
<br>
<br><font size=2 face="sans-serif">using namespace std ;</font>
<br>
<br><font size=2 face="sans-serif">void main()</font>
<br><font size=2 face="sans-serif">{</font>
<br><font size=2 face="sans-serif">    const int VECTOR_SIZE
= 4;</font>
<br>
<br><font size=2 face="sans-serif">    // Define a template class
vector of strings</font>
<br><font size=2 face="sans-serif">    typedef vector<string>
StrVector;</font>
<br>
<br><font size=2 face="sans-serif">    // Define an iterator
for template class vector of strings</font>
<br><font size=2 face="sans-serif">    typedef StrVector::iterator
StrVectorIt;</font
 
 
 

possible bug with STL prev_permutation in VC++7.1 professional

Post by P.J. Plaug » Thu, 04 Mar 2004 19:09:40


At last, a solid test case! I've suspected for years that the
permutations weren't always safe when two elements have equivalent
ordering. Unfortunately, I kept reading next_permutation and found
nothing wrong. I've appended corrected code for the two versions of
prev_permutation in <algorithm> below. The /// lines are erroneous;
each such line is followed by its correction. The V6 headers have
exactly the same bug, and fix -- you just have to map the fix to
the older names.

Thanks very much.

P.J. Plauger
Dinkumware, Ltd.
http://www.yqcomputer.com/


-------

// TEMPLATE FUNCTION prev_permutation
template<class _BidIt> inline
bool prev_permutation(_BidIt _First, _BidIt _Last)
{ // reverse permute and test for pure descending, using operator<
_BidIt _Next = _Last;
if (_First == _Last || _First == --_Next)
return (false);
for (; ; )
{ // find rightmost element not smaller than successor
_BidIt _Next1 = _Next;
/// if (!(*--_Next < *_Next1))
if (*_Next1 < *--_Next)
{ // swap with rightmost element that's not smaller, flip suffix
_BidIt _Mid = _Last;
/// for (; *_Next < *--_Mid; )
for (; !(*--_Mid < *_Next); )
;
std::iter_swap(_Next, _Mid);
std::reverse(_Next1, _Last);
return (true);
}

if (_Next == _First)
{ // pure ascending, flip all
std::reverse(_First, _Last);
return (false);
}
}
}

// TEMPLATE FUNCTION prev_permutation WITH PRED
template<class _BidIt,
class _Pr> inline
bool prev_permutation(_BidIt _First, _BidIt _Last, _Pr _Pred)
{ // reverse permute and test for pure descending, using _Pred
_BidIt _Next = _Last;
if (_First == _Last || _First == --_Next)
return (false);

for (; ; )
{ // find rightmost element not smaller than successor
_BidIt _Next1 = _Next;
/// if (!_Pred(*--_Next, *_Next1))
if (_Pred(*_Next1, *--_Next))
{ // swap with rightmost element that's not smaller, flip suffix
_BidIt _Mid = _Last;
/// for (; _Pred(*_Next, *--_Mid); )
for (; !_Pred(*--_Mid, *_Next); )
;
std::iter_swap(_Next, _Mid);
std::reverse(_Next1, _Last);
return (true);
}

if (_Next == _First)
{ // pure ascending, flip all
std::reverse(_First, _Last);
return (false);
}
}
}