blob: 995bf3a1091935a26b41bcb26ba7b61736970134 [file] [log] [blame]
<!--
Licensed to the Apache Software Foundation (ASF) under one or more
contributor license agreements. See the NOTICE file distributed
with this work for additional information regarding copyright
ownership. The ASF licenses this file to you under the Apache
License, Version 2.0 (the License); you may not use this file
except in compliance with the License. You may obtain a copy of
the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied. See the License for the specific language governing
permissions and limitations under the License.
Copyright 1999-2007 Rogue Wave Software, Inc.
-->
<HTML>
<HEAD>
<TITLE>next_permutation()</TITLE>
<LINK REL=StyleSheet HREF="../rw.css" TYPE="text/css" TITLE="Apache stdcxx Stylesheet"></HEAD>
<BODY BGCOLOR=#FFFFFF>
<A HREF="new-h.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="not1.html"><IMG SRC="images/bnext.gif" WIDTH=25 HEIGHT=21 ALT="Next file" BORDER=O></A><DIV CLASS="DOCUMENTNAME"><B>Apache C++ Standard Library Reference Guide</B></DIV>
<H2>next_permutation()</H2>
<P><B>Library:</B>&nbsp;&nbsp;<A HREF="2-9.html">Algorithms</A></P>
<PRE><HR><B><I>Function</I></B><HR></PRE>
<UL>
<LI><A HREF="#sec1">Local Index</A></LI>
<LI><A HREF="#sec2">Summary</A></LI>
<LI><A HREF="#sec3">Synopsis</A></LI>
<LI><A HREF="#sec4">Description</A></LI>
<LI><A HREF="#sec5">Complexity</A></LI>
<LI><A HREF="#sec6">Example</A></LI>
<LI><A HREF="#sec7">See Also</A></LI>
<LI><A HREF="#sec8">Standards Conformance</A></LI>
</UL>
<A NAME="sec1"><H3>Local Index</H3></A>
No Entries
<A NAME="sec2"><H3>Summary</H3></A>
<P>Algorithm that generates successive permutations of a sequence based on an ordering function </P>
<A NAME="sec3"><H3>Synopsis</H3></A>
<PRE>#include &lt;algorithm&gt;
namespace std {
template &lt;class BidirectionalIterator&gt;
bool next_permutation(BidirectionalIterator start,
BidirectionalIterator finish);
template &lt;class BidirectionalIterator, class Compare&gt;
bool next_permutation(BidirectionalIterator start,
BidirectionalIterator finish,
Compare comp);
}
</PRE>
<A NAME="sec4"><H3>Description</H3></A>
<P>The permutation-generating algorithms, <SAMP>next_permutation()</SAMP> and <SAMP><A HREF="prev-permutation.html">prev_permutation()</A></SAMP>, assume that the set of all permutations of the elements in a sequence is lexicographically sorted with respect to <SAMP>operator&lt;()</SAMP> or the binary predicate <SAMP>comp</SAMP>. For example, if a sequence includes the integers 1 2 3, that sequence has six permutations. In order from first to last, they are: 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, and 3 2 1. </P>
<P>The <SAMP>next_permutation()</SAMP> algorithm takes a sequence defined by the range <SAMP>[start, finish)</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, <SAMP>next_permutation()</SAMP> transforms the permutation into its "first" permutation and returns <SAMP>false</SAMP>. <SAMP>next_permutation()</SAMP> does the transformation according to the lexicographical ordering defined by either <SAMP>operator&lt;()</SAMP> (used in the first version of the algorithm) or the binary predicate <SAMP>comp</SAMP> (which is user-supplied in the second version of the algorithm). </P>
<P>For example, if the sequence defined by <SAMP>[start, finish)</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="sec5"><H3>Complexity</H3></A>
<P>At most <SAMP>(finish - start)/2 </SAMP>swaps are performed.</P>
<A NAME="sec6"><H3>Example</H3></A>
<UL><PRE>//
// permute.cpp
//
#include &lt;algorithm&gt; // for next_permutation, prev_permutation
#include &lt;functional&gt; // for less
#include &lt;iostream&gt; // for cout, endl
#include &lt;numeric&gt; // for accumulate
#include &lt;vector&gt; // for vector
int main ()
{
typedef std::vector&lt;int, std::allocator&lt;int&gt; &gt; IntVec;
typedef std::vector&lt;char, std::allocator&lt;char&gt; &gt; CharVec;
// Initialize a vector using an array of integers.
const IntVec::value_type a1[] = { 0, 0, 0, 0, 1,
0, 0, 0, 0, 0 };
const CharVec::value_type a2[] = "abcdefghji";
// Create the initial set and copies for permuting.
IntVec m1 (a1, a1 + sizeof a1 / sizeof *a1);
IntVec prev_m1 (10);
IntVec next_m1 (10);
CharVec m2 (a2, a2 + sizeof a2 / sizeof *a2 - 1);
CharVec prev_m2 (10);
CharVec next_m2 (10);
std::copy (m1.begin (), m1.end (), prev_m1.begin ());
std::copy (m1.begin (), m1.end (), next_m1.begin ());
std::copy (m2.begin (), m2.end (), prev_m2.begin ());
std::copy (m2.begin (), m2.end (), next_m2.begin ());
// Create permutations.
typedef std::less&lt;IntVec::value_type&gt; IntLess;
typedef std::less&lt;CharVec::value_type&gt; CharLess;
std::prev_permutation (prev_m1.begin (), prev_m1.end (),
IntLess ());
std::next_permutation (next_m1.begin (), next_m1.end (),
IntLess ());
std::prev_permutation (prev_m2.begin (), prev_m2.end (),
CharLess ());
std::next_permutation (next_m2.begin (), next_m2.end (),
CharLess ());
// Output results.
typedef std::ostream_iterator&lt;IntVec::value_type, char,
std::char_traits&lt;char&gt; &gt;
IntOSIter;
typedef std::ostream_iterator&lt;CharVec::value_type, char,
std::char_traits&lt;char&gt; &gt;
CharOSIter;
std::cout &lt;&lt; "Example 1: \n Original values: ";
std::copy (m1.begin (), m1.end (),
IntOSIter (std::cout, " "));
std::cout &lt;&lt; "\n Previous permutation: ";
std::copy (prev_m1.begin (), prev_m1.end (),
IntOSIter (std::cout, " "));
std::cout &lt;&lt; "\n Next Permutation: ";
std::copy (next_m1.begin (), next_m1.end (),
IntOSIter (std::cout, " "));
std::cout &lt;&lt; "\n\nExample 2: \n ";
&lt;&lt; "Original values: ";
std::copy (m2.begin (), m2.end (),
CharOSIter (std::cout, " "));
std::cout &lt;&lt; "\n Previous Permutation: ";
std::copy (prev_m2.begin (), prev_m2.end (),
CharOSIter (std::cout, " "));
std::cout &lt;&lt; "\n Next Permutation: ";
std::copy (next_m2.begin (), next_m2.end (),
CharOSIter (std::cout, " "));
std::cout &lt;&lt; std::endl &lt;&lt; std::endl;
return 0;
}
Program Output:
</PRE></UL>
<UL><PRE>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></UL>
<A NAME="sec7"><H3>See Also</H3></A>
<P><SAMP><A HREF="prev-permutation.html">prev_permutation()</A></SAMP></P>
<A NAME="sec8"><H3>Standards Conformance</H3></A>
<P><I>ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.3.9</I></P>
<BR>
<HR>
<A HREF="new-h.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="not1.html"><IMG SRC="images/bnext.gif" WIDTH=20 HEIGHT=21 ALT="Next file" BORDER=O></A>
<!-- Google Analytics tracking code -->
<script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
_uacct = "UA-1775151-1";
urchinTracker();
</script>
<!-- end of Google Analytics tracking code -->
</BODY>
</HTML>