如何样求数组的一个全排列
怎么样求数组的一个全排列。
比如说给个整数数组，要求打印出其内容的全排列。
int a[] = { 1, 2, 3 };
它的全排列是，
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1
...
请问这个算法如何设计 ？
------解决方案--------------------
用回溯吧
------解决方案--------------------
1、排序，避免相同数字产生的同样的序列；
2、简单迭代或递归，通过k-1个元素的全排列求k个元素的全排列。
------解决方案--------------------
全排列的生成算法
2008年04月25日 星期五 下午 03:23
全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。任何n个字符集的排列都可以与1～n的n个数字的排列一一对应，因此在此就以n个数字的排列为例说明排列的生成法。
n个字符的全体排列之间存在一个确定的线性顺序关系。所有的排列中除最后一个排列外，都有一个后继；除第一个排列外，都有一个前驱。每个排列的后继都可以从 它 的前驱经过最少的变化而得到，全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法。
全排列的生成法通常有以下几种：
字典序法
递增进位数制法
递减进位数制法
邻位交换法
n进位制法
递归类算法
1.字典序法
字典序法中，对于数字1、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是 54321。
字典序算法如下：
设P是1～n的一个全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn
1）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即 j=max{i
------解决方案--------------------
pi<pi+1}
2）在pj的右边的数字中，找出所有比pj大的数中最小的数字pk，即 k=max{i
------解决方案--------------------
pi>pj}（右边的数从右至左是递增的，因此k是所有大于pj的数字中序号最大者）
3）对换pi，pk
4）再将pj+1......pk-1pkpk+1pn倒转得到排列p'=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，这就是排列p的下一个下一个排列。
例如839647521是数字1～9的一个排列。从它生成下一个排列的步骤如下：
自右至左找出排列中第一个比右边数字小的数字4 839647521
在该数字后的数字中找出比4大的数中最小的一个5 839647521
将5与4交换 839657421
将7421倒转 839651247
所以839647521的下一个排列是839651247。
程序代码如下：
Private Sub Dict(p() As Integer, ByVal n As Integer)
Dim i As Integer, j As Integer
OutL p
i = n - 1
Do While i > 0
If p(i) < p(i + 1) Then
For j = n To i + 1 Step -1 '从排列右端开始
If p(i) <= p(j) Then Exit For '找出递减子序列
Next
Swap p(i), p(j) '将递减子序列前的数字与序列中比它大的第一个数交换
For j = n To 1 Step -1 '将这部分排列倒转
i = i + 1
If i >= j Then Exit For
Swap p(i), p(j)
Next
OutL p '输出一个排列
i = n
End If
i = i - 1
Loop
End Sub
Swap p(i), p(j)是交换两个元素的子过程，OutL p是输出排列的子过程。
2.递增进位数制法
在递增进位制数法中，从一个排列求另一个排列需要用到中介数。如果用 ki表示排列p1p2...pi...pn中元素pi的右边比pi小的数的个数，则排列的中介数就是对应的排列k1 ...... ki...... kn-1。
例如排列839647521的中介数是72642321，7、2、6、......分别是排列中数字8、3、9、......的右边比它小的数字个数。
中介数是计算排列的中间环节。已知一个排列，要求下一个排列，首先确定其中介数，一个排列的后继，其中介数是原排列中介数加1，需要注意的是，如果中介数 的末位kn-1+1=2，则要向前进位，一般情形，如果ki+1=n-i+1，则要进位，这就是所谓的递增进位制。例如排列839647521的中介数是 72642321，则下一个排列的中介数是67342221+1=67342300（因为1+1=2，所以向前进位，2+1=3，又发生进位，所以下一个 中介数是67342300）。
得到中介数后，可根据它还原对应得排列。算法如下：
中介数k1、k2、......、kn-1的各位数字顺序表示排列中的数字n、n-1、......、2在排列中距右端的的空位数，因此，要按k1、 k2、......、kn-1的值从右向左确定n、n-1、......、2的位置，并逐个放置在排列中：i放在右起的ki+1位，如果某位已放有数字， 则该位置不算在内，最后一个空位放1。
因此从67342300可得到排列849617523，它就是839647521的后一个排列。因为9最先放置，k1=6，9放在右起第7位，空出6个空位，然后是放8，k2=7，8放在右起第8位，但9占用一位，故8应放在右起第9位，余类推。
比如说给个整数数组，要求打印出其内容的全排列。
int a[] = { 1, 2, 3 };
它的全排列是，
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1
...
请问这个算法如何设计 ？
------解决方案--------------------
用回溯吧
------解决方案--------------------
1、排序，避免相同数字产生的同样的序列；
2、简单迭代或递归，通过k-1个元素的全排列求k个元素的全排列。
------解决方案--------------------
全排列的生成算法
2008年04月25日 星期五 下午 03:23
全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。任何n个字符集的排列都可以与1～n的n个数字的排列一一对应，因此在此就以n个数字的排列为例说明排列的生成法。
n个字符的全体排列之间存在一个确定的线性顺序关系。所有的排列中除最后一个排列外，都有一个后继；除第一个排列外，都有一个前驱。每个排列的后继都可以从 它 的前驱经过最少的变化而得到，全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法。
全排列的生成法通常有以下几种：
字典序法
递增进位数制法
递减进位数制法
邻位交换法
n进位制法
递归类算法
1.字典序法
字典序法中，对于数字1、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是 54321。
字典序算法如下：
设P是1～n的一个全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn
1）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即 j=max{i
------解决方案--------------------
pi<pi+1}
2）在pj的右边的数字中，找出所有比pj大的数中最小的数字pk，即 k=max{i
------解决方案--------------------
pi>pj}（右边的数从右至左是递增的，因此k是所有大于pj的数字中序号最大者）
3）对换pi，pk
4）再将pj+1......pk-1pkpk+1pn倒转得到排列p'=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，这就是排列p的下一个下一个排列。
例如839647521是数字1～9的一个排列。从它生成下一个排列的步骤如下：
自右至左找出排列中第一个比右边数字小的数字4 839647521
在该数字后的数字中找出比4大的数中最小的一个5 839647521
将5与4交换 839657421
将7421倒转 839651247
所以839647521的下一个排列是839651247。
程序代码如下：
Private Sub Dict(p() As Integer, ByVal n As Integer)
Dim i As Integer, j As Integer
OutL p
i = n - 1
Do While i > 0
If p(i) < p(i + 1) Then
For j = n To i + 1 Step -1 '从排列右端开始
If p(i) <= p(j) Then Exit For '找出递减子序列
Next
Swap p(i), p(j) '将递减子序列前的数字与序列中比它大的第一个数交换
For j = n To 1 Step -1 '将这部分排列倒转
i = i + 1
If i >= j Then Exit For
Swap p(i), p(j)
Next
OutL p '输出一个排列
i = n
End If
i = i - 1
Loop
End Sub
Swap p(i), p(j)是交换两个元素的子过程，OutL p是输出排列的子过程。
2.递增进位数制法
在递增进位制数法中，从一个排列求另一个排列需要用到中介数。如果用 ki表示排列p1p2...pi...pn中元素pi的右边比pi小的数的个数，则排列的中介数就是对应的排列k1 ...... ki...... kn-1。
例如排列839647521的中介数是72642321，7、2、6、......分别是排列中数字8、3、9、......的右边比它小的数字个数。
中介数是计算排列的中间环节。已知一个排列，要求下一个排列，首先确定其中介数，一个排列的后继，其中介数是原排列中介数加1，需要注意的是，如果中介数 的末位kn-1+1=2，则要向前进位，一般情形，如果ki+1=n-i+1，则要进位，这就是所谓的递增进位制。例如排列839647521的中介数是 72642321，则下一个排列的中介数是67342221+1=67342300（因为1+1=2，所以向前进位，2+1=3，又发生进位，所以下一个 中介数是67342300）。
得到中介数后，可根据它还原对应得排列。算法如下：
中介数k1、k2、......、kn-1的各位数字顺序表示排列中的数字n、n-1、......、2在排列中距右端的的空位数，因此，要按k1、 k2、......、kn-1的值从右向左确定n、n-1、......、2的位置，并逐个放置在排列中：i放在右起的ki+1位，如果某位已放有数字， 则该位置不算在内，最后一个空位放1。
因此从67342300可得到排列849617523，它就是839647521的后一个排列。因为9最先放置，k1=6，9放在右起第7位，空出6个空位，然后是放8，k2=7，8放在右起第8位，但9占用一位，故8应放在右起第9位，余类推。