字典序法求解全排列问题

对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的

字符的先后。

[例]字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:
123,132,213,231,312,321。
※※ 一个全排列可看做一个字符串，字符串可有前缀、后缀。

生成给定全排列的下一个排列:
所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。

[例]  839647521是1--9的排列。1—9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。

一般而言，设P是[1,n]的一个全排列

找出最远的一对(Pi

 

关于组合数组的字典序生成法是这样进行的：(最简洁)

　　对于给定的一个数，首先从右边找到第一个相邻"逆序对"，现假设下一个要找的数比这个数大，且中间没有一个数比前者大、比后者小。那么这个"逆序对"的定义是就是满足
num[ i ]< num[ i+ 1 ]（假设这个整数是以数组的形式存储的），然后再重新从右边起找出第一个比那个"逆序对"的较小者 要大的数，交换他们，再将那个较小数下标后面的子数组反转。。。。。

STL有个这样的函数：

这是一道典型的全排列问题。可以用STL的next_permutation()函数，标准库全排列next_permutation()的

返回值:bool类型

分析next_permutation函数执行过程:
假设数列 d1,d2,d3,d4……范围由[first,last)标记，调用next_permutation使数列逐次增大，这个递增过

程按照字典序。

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int a[] = {1,2,3};
    do
    {
        cout << a[0] << " " << a[1] << " " << a[2] << endl;
    }
    while (next_permutation(a,a+3));//while放在前面的话 要考虑如何输出第一个 1 2 3，因为

数组一直在递增
    return 0;
}
/*
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Press any key to continue*/