12,699,531 members (34,331 online)

69.8K views
25 bookmarked
Posted

# Implementing Permutation Variations

, 14 Jul 2004 CPOL
Several enhanced permutation algorithms created in iterative or recursive solution.
 ```// ============================================================================ // File: StlPermu.cpp - Testing StlPermutation // Author: Zuoliu Ding, May 2004 // ============================================================================ #include #include #include #include using namespace std; typedef map Position_Map; typedef pair Position_Pair; // STL: TEMPLATE FUNCTION next_permutation in algorithm standard header // permute and test for pure ascending, using operator< template inline bool _next_permutation(_BidIt _First, _BidIt _Last, Position_Map* pMap/*=NULL*/) { _BidIt _Next = _Last; if (_First ==_Last || _First == --_Next) return (false); for (; ; ) { _BidIt _Next1 = _Next; if (pMap? (*pMap)[*--_Next] < (*pMap)[*_Next1]: *--_Next < *_Next1) { _BidIt _Mid = _Last; for (; !(pMap? (*pMap)[*_Next] < (*pMap)[*--_Mid]: *_Next < *--_Mid);); std::iter_swap(_Next, _Mid); std::reverse(_Next1, _Last); return (true); } if (_Next == _First) { std::reverse(_First, _Last); return (false); } } } // ============================================================================ // Function: StlPermutation - using STL function next_permutation // Description: Generate all Permuted strings for an input string // Parameter: sz: [in] an input string. // Return: A vector of all Permuted strings. // Note: STL next_permutation permutes the string sz to the // lexicographically next string as an arrangement, and then // returns true. If the string sz is in descending order then // it returns false. // ============================================================================ vector StlPermutation(const char* sz, bool bOrdered/*=true*/) { vector v; string s = sz; Position_Map mapPos; if (!bOrdered) for (unsigned int i=0; i inline bool _next_permutation(_BidIt _First, _BidIt _Last) { _BidIt _Next = _Last; if (_First ==_Last || _First == --_Next) return (false); for (; ; ) { // find rightmost element smaller than successor _BidIt _Next1 = _Next; if (*--_Next < *_Next1) { // swap with rightmost element that's smaller _BidIt _Mid = _Last; for (; !(*_Next < *--_Mid);) ; std::iter_swap(_Next, _Mid); std::reverse(_Next1, _Last); return (true); } if (_Next == _First) { // pure descending, flip all std::reverse(_First, _Last); return (false); } } } vector StlPermutation(const char* sz) { vector v; string s = sz; do v.insert(v.end(), s); while (_next_permutation(s.begin(), s.end())); return v; } */ ```

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.