列出全排列的初始思想是什么？全排列的字典序法是什么？

列出全排列的初始思想：

解决一个算法问题，我比较习惯于从基本的想法做起，我们先回顾一下我们自己是如何写一组数的全排列的：1，3，5，9(为了方便，下面我都用数进行全排列而不是字符)。

【1，3，5，9】(第一个)

首先保持第一个不变，对【3，5，9】进行全排列。

同样地，我们先保持3不变，对【5，9】进行全排列。

保持5不变，对9对进行全排列，由于9只有一个，它的排列只有一种：9。

故排列为【1，3，5，9】

接下来5不能以5打头了，5，9相互交换，得到

【1，3，9，5】

此时5，9的情况都写完了，不能以3打头了，得到

1，5，3，9

1，5，9，3

1，9，3，5

1，9，5，3

这样，我们就得到了1开头的所有排列，这是我们一般的排列数生成的过程。再接着是以3、5、9打头，得到全排列。

我们现在做这样的一个假设，假设给定的一些序列中第一位都不相同，那么就可以认定说这些序列一定不是同一个序列，这是一个很显然的问题。有了上面的这一条结论，我们就可以同理得到如果在第一位相同，可是第二位不同，那么在这些序列中也一定都不是同一个序列。

那么，这个问题可以这样来看。对

我们获得了在第一个位置上的所有情况之后(注：是所有的情况)，对每一种情况，抽去序列中的第一个位置，那么对于剩下的序列可以看成是一个全新的序列

全排列的字典序法是什么?

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

[例]字符集{1,2,3},较小的数字较先,

这样按字典序生成的全排列是:123,132,213,231,312,321。

[注意] 一个全排列可看做一个字符串，字符串可有前缀、后缀。

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

[例]839647521是1--9的排列。

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