STL学习笔记之next_permutation函数

约定不等于承诺〃 2022-11-01 13:50 130阅读 0赞

# STL库中的next\_permutation函数详解 #

# std::next\_permutation C++官网讲解 #

<table> 
 <thead> 
  <tr> 
   <th align="right">default (1)</th> 
   <th><code>template &lt;class BidirectionalIterator&gt; bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);</code></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="right">custom (2)</td> 
   <td><code>template &lt;class BidirectionalIterator, class Compare&gt; bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);</code></td> 
  </tr> 
 </tbody> 
</table>

Transform range to next permutation

Rearranges the elements in the range `[first,last)` into the next *[lexicographically][] greater* permutation.

A permutation is each one of the `N!` possible arrangements the elements can take (where N is the number of elements in the range). Different permutations can be ordered according to how they compare *[lexicographicaly][lexicographically]* to each other; The first such-sorted possible permutation (the one that would compare *lexicographically smaller* to all other permutations) is the one which has all its elements sorted in ascending order, and the largest has all its elements sorted in descending order.

The comparisons of individual elements are performed using either `operator<` for the first version, or comp for the second.

If the function can determine the next higher permutation, it rearranges the elements as such and returns `true`. If that was not possible (because it is already at the largest possible permutation), it rearranges the elements according to the first permutation (sorted in ascending order) and returns `false`.

### Parameters ###

*  first, last
    
    [Bidirectional iterators][] to the initial and final positions of the sequence. The range used is `[first,last)`, which contains all the elements between first and last, including the element pointed by first but not the element pointed by last. BidirectionalIterator shall point to a type for which [swap][] is properly defined.
 *  comp
    
    Binary function that accepts two arguments of the type pointed by BidirectionalIterator, and returns a value convertible to `bool`. The value returned indicates whether the first argument is considered to go before the second in the specific *strict weak ordering* it defines. The function shall not modify any of its arguments. This can either be a function pointer or a function object.

### Return value ###

`true` if the function could rearrange the object as a lexicographicaly greater permutation.  
Otherwise, the function returns `false` to indicate that the arrangement is not greater than the previous, but the lowest possible (sorted in ascending order).

### Example ###

// next_permutation example
    #include <iostream> // std::cout
    #include <algorithm> // std::next_permutation, std::sort
    
    int main () { 
      int myints[] = { 1,2,3};
    
      std::sort (myints,myints+3);
    
      std::cout << "The 3! possible permutations with 3 elements:\n";
      do { 
        std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
      } while ( std::next_permutation(myints,myints+3) );
    
      std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
    
      return 0;
    }

Output:

The 3! possible permutations with 3 elements: 
    1 2 3 
    1 3 2 
    2 1 3 
    2 3 1 
    3 1 2 
    3 2 1 
    After loop: 1 2 3

### Complexity ###

Up to linear in half the [distance][] between first and last (in terms of actual swaps).

### Data races ###

The objects in the range `[first,last)` are modified.

### Exceptions ###

Throws if any element swap throws or if any operation on an iterator throws.  
Note that invalid arguments cause *undefined behavior*.

--------------------

STL提供求下一个排列组合的函数next\_permutation()。例如3个字符a、b、c组成的序列，此函数能按照字典序返回6个排列，即abc、acb、bac、bca、cab、cba。

返回值：如果没有下一个排列组合，返回false，否则返回true。每次执行此函数一次，就会把新的排列放到原来的空间里。

复杂度： O ( n ) O(n) O(n)

这个函数的小实例在上面的英文版里。

--------------------

# 练习题：HDU1027 #

## Problem Description ##

Now our hero finds the door to the BEelzebub feng5166. He opens the door and finds feng5166 is about to kill our pretty Princess. But now the BEelzebub has to beat our hero first. feng5166 says, “I have three question for you, if you can work them out, I will release the Princess, or you will be my dinner, too.” Ignatius says confidently, “OK, at last, I will save the Princess.”

“Now I will show you the first problem.” feng5166 says, “Given a sequence of number 1 to N, we define that 1,2,3…N-1,N is the smallest sequence among all the sequence which can be composed with number 1 to N(each number can be and should be use only once in this problem). So it’s easy to see the second smallest sequence is 1,2,3…N,N-1. Now I will give you two numbers, N and M. You should tell me the Mth smallest sequence which is composed with number 1 to N. It’s easy, isn’t is? Hahahahaha…”  
Can you help Ignatius to solve this problem?

## Input ##

The input contains several test cases. Each test case consists of two numbers, N and M(1<=N<=1000, 1<=M<=10000). You may assume that there is always a sequence satisfied the BEelzebub’s demand. The input is terminated by the end of file.

## Output ##

For each test case, you only have to output the sequence satisfied the BEelzebub’s demand. When output a sequence, you should print a space between two numbers, but do not output any spaces after the last number.

## Sample Input ##

6 4
    11 8

## Sample Output ##

1 2 3 5 6 4
    1 2 3 4 5 6 7 9 8 11 10

## Author ##

Ignatius.L

--------------------

# AC CODE #

#include <iostream>
    #include <algorithm>
    #include <vector>
    
    int a[1001];
    using namespace std;
    
    int main()
    { 
        int n, m;
        while (cin >> n >> m)
        { 
            for (int i = 1; i <= n; i++)
                a[i] = i;
            int b = 1;
            do
            { 
                if (b == m)
                    break;
                b++;
            } while (next_permutation(a + 1, a + n + 1));
            for (int i = 1; i < n; i++)
                cout << a[i] << " ";
            cout << a[n] << endl;
        }
        return 0;
    }

[lexicographically]: http://www.cplusplus.com/lexicographical_compare
[Bidirectional iterators]: http://www.cplusplus.com/BidirectionalIterator
[swap]: http://www.cplusplus.com/swap
[distance]: http://www.cplusplus.com/distance