📄 nex_1756.htm
字号:
<HTML><TITLE>next_permutation</TITLE><BODY>
<A HREF="ref.htm"><IMG SRC="images/banner.gif"></A>
<P><STRONG>Click on the banner to return to the Class Reference home page.</STRONG></P>
<P>©Copyright 1996 Rogue Wave Software</P>
<H2>next_permutation</H2>
<HR><PRE> Algorithm</PRE><HR>
<A NAME="Summary"><H3>Summary</H3></A>
<P>Generate successive permutations of a sequence based on an ordering function. </P>
<H3>Contents</H3>
<UL>
<A HREF="#Synopsis"><LI>Synopsis</LI></A>
<A HREF="#Description"><LI>Description</LI></A>
<A HREF="#Complexity"><LI>Complexity</LI></A>
<A HREF="#Example"><LI>Example</LI></A>
<A HREF="#Warning"><LI>Warning</LI></A>
<A HREF="#See Also"><LI>See Also</LI></A>
</UL>
<A NAME="Synopsis"><H3>Synopsis</H3></A>
<PRE>#include <algorithm></PRE>
<PRE>
template <class BidirectionalIterator>
bool <B>next_permutation</B> (BidirectionalIterator first,
BidirectionalIterator last);
template <class BidirectionalIterator, class Compare>
bool <B>next_permutation</B> (BidirectionalIterator first,
BidirectionalIterator last, Compare comp);</PRE>
<A NAME="Description"><H3>Description</H3></A>
<P>The permutation-generating algorithms (<B><I>next_permutation</B></I> and <A HREF="pre_1548.htm"><B><I>prev_permutation</B></I></A>) assume that the set of all permutions of the elements in a sequence is lexicographically sorted with respect to <SAMP>operator<</SAMP> or <SAMP>comp</SAMP>. So, for example, if a sequence includes the integers 1 2 3, that sequence has six permutations, which, in order from first to last are: 1 2 3 , 1 3 2, 2 1 3, 2 3 1, 3 1 2, and 3 2 1. </P>
<P>The <B><I>next_permutation</B></I> algorithm takes a sequence defined by the range <SAMP>[first, last)</SAMP> and transforms it into its next permutation, if possible. If such a permutation does exist, the algorithm completes the transformation and returns <SAMP>true</SAMP>. If the permutation does not exist, <B><I>next_permutation</B></I> returns <SAMP>false</SAMP>, and transforms the permutation into its "first" permutation (according to the lexicographical ordering defined by either <SAMP>operator<</SAMP>, the default used in the first version of the algorithm,or <SAMP>comp</SAMP>, which is user-supplied in the second version of the algorithm.) </P>
<P>For example, if the sequence defined by <SAMP>[first, last)</SAMP> contains the integers 3 2 1 (in that order), there is <I>not</I> a "next permutation." Therefore, the algorithm transforms the sequence into its first permutation (1 2 3) and returns <SAMP>false</SAMP>.</P>
<A NAME="Complexity"><H3>Complexity</H3></A>
<P>At most <SAMP>(last - first)/2 </SAMP>swaps are performed.</P>
<A NAME="Example"><H3>Example</H3></A>
<PRE>//
// permute.cpp
//
#include <numeric> //for accumulate
#include <vector> //for vector
#include <functional> //for less
#include <iostream.h>
int main()
{
//Initialize a vector using an array of ints
int a1[] = {0,0,0,0,1,0,0,0,0,0};
char a2[] = "abcdefghji";</PRE><PRE> //Create the initial set and copies for permuting
vector<int> m1(a1, a1+10);
vector<int> prev_m1((size_t)10), next_m1((size_t)10);
vector<char> m2(a2, a2+10);
vector<char> prev_m2((size_t)10), next_m2((size_t)10);</PRE><PRE> copy(m1.begin(), m1.end(), prev_m1.begin());
copy(m1.begin(), m1.end(), next_m1.begin());
copy(m2.begin(), m2.end(), prev_m2.begin());
copy(m2.begin(), m2.end(), next_m2.begin());</PRE><PRE> //Create permutations
prev_permutation(prev_m1.begin(),
prev_m1.end(),less<int>());
<B> next_permutation</B>(next_m1.begin(),
next_m1.end(),less<int>());
prev_permutation(prev_m2.begin(),
prev_m2.end(),less<int>());
<B> next_permutation</B>(next_m2.begin(),
next_m2.end(),less<int>());</PRE><PRE> //Output results
cout << "Example 1: " << endl << " ";
cout << "Original values: ";
copy(m1.begin(),m1.end(),
ostream_iterator<int>(cout," "));
cout << endl << " ";
cout << "Previous permutation: ";
copy(prev_m1.begin(),prev_m1.end(),
ostream_iterator<int>(cout," "));</PRE><PRE> cout << endl<< " ";
cout << "Next Permutation: ";
copy(next_m1.begin(),next_m1.end(),
ostream_iterator<int>(cout," "));
cout << endl << endl;</PRE><PRE> cout << "Example 2: " << endl << " ";
cout << "Original values: ";
copy(m2.begin(),m2.end(),
ostream_iterator<char>(cout," "));
cout << endl << " ";
cout << "Previous Permutation: ";
copy(prev_m2.begin(),prev_m2.end(),
ostream_iterator<char>(cout," "));
cout << endl << " ";</PRE><PRE> cout << "Next Permutation: ";
copy(next_m2.begin(),next_m2.end(),
ostream_iterator<char>(cout," "));
cout << endl << endl;
return 0;
}
Output :
Example 1:
Original values: 0 0 0 0 1 0 0 0 0 0
Previous permutation: 0 0 0 0 0 1 0 0 0 0
Next Permutation: 0 0 0 1 0 0 0 0 0 0
Example 2:
Original values: a b c d e f g h j i
Previous Permutation: a b c d e f g h i j
Next Permutation: a b c d e f g i h j
</PRE>
<A NAME="Warning"><H3>Warning</H3></A>
<P>If your compiler does not support default template parameters, the you need to always supply the <SAMP>Allocator</SAMP> template argument. For instance, you will need to write :</P>
<P><SAMP>vector<int, allocator></SAMP></P>
<P>instead of :</P>
<P><SAMP>vector<int></SAMP></P>
<A NAME="See Also"><H3>See Also</H3></A>
<P><A HREF="per_9476.htm"><B><I>permutation</B></I></A></P>
<HR>
<A HREF="Neg_5086.htm"><IMG SRC="images/prev.gif"></A> <A HREF="ref.htm#contents"><IMG SRC="images/toc.gif"></A> <A HREF="not_6483.htm"><IMG SRC="images/next.gif"></A></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -