12,073,325 members (67,337 online)

67.1K views
24 bookmarked
Posted

# Implementing Permutation Variations

, 14 Jul 2004 CPOL
Several enhanced permutation algorithms created in iterative or recursive solution.
 permute_demo.zip // ============================================================================ // 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.

## Share

 Software Developer United States
An Adjunct Faculty and Software Developer in Los Angeles and Orange County, CA

* Typical articles published in Dr. Dobb’s Journal and Windows Developer Magazine:

- A Silent Component Update for Internet Explorer
- Silent Application Update
- An MDI-Style Web Browser and Load Spy Monitor
- Implementing Wireless Print for WinNT/Win2K
- Multi-State Checkbox Tree Views
- A Generic Tool Tip Class
- An Easy Way to Add Tool Tips to Any MFC Control