邻位对换法生成全排列

对于集合

S={a1,a2,...,an} S=\{a_1, a_2, ..., a_n\}

若已知前 n1n-1 个元素的全排列,则 nn 个元素的全排列

pi={p1,p2,...,p(n1)!} p_i=\{p_1,p_2,...,p_{(n-1)!}\}

可以这样生成:将 ana_n 插入 pip_i 不同位置中,由此,得到集合 SS 的全排列

为什么这样操作能得到集合 SS 的全排列?因为每个 pip_i 的可能插入位置为 nn 个,所以总数是 n!n! 又因为每个 pip_i 是不同的,因此,得到的排列必然没有重复

插入法有一个缺点:为了产生 nn 个元素的排列,必须知道并存储所有 n1n-1 个元素的排列,然后才能产生出所有 nn 阶排列

依赖插入法能够生成全排列的事实,但邻位对换法不需要知道 n1n-1 个元素的排列,只需要从某一个初始排列状态开始,进行特定的相邻元素交换即可生成全排列

假设算法对 nn 个元素能生成全排列,只需要证明其对 n+1n+1 个元素,也能生成全排列,对于新进来的元素,将其认为值最大,插入最右方,每次从右移到左,或者改变方向后从左移到右,就可以认为对于一个排列从不同位置插入生成一个新的排列,而原本 nn 个元素是全排列的,因此对于 n+1n+1 个元素也是全排列的,因此邻位对换法能生成全排列

S={1,2,3,4}S=\{1, 2, 3, 4\} 为例。若 {1,2,3}\{1, 2, 3\} 的全排列为:

p1p_1 p2p_2 p3p_3 p4p_4 p5p_5 p6p_6
123 132 312 321 231 213

那么,将 44 按从尾到头的方式插入每一个排列,就得到:

观察——

第 1 列,从上往下
第 2 列,从下往上
第 3 列,从上往下
...
一直走到最后一列,当前方向上的最后一格

规律:路径上的任一排列是前一个排列交换两个相邻元素而得

比如 1423 ,它是由 1243 通过 4 与 2 换位得到

即:一个排列,由上一排列通过交换该排列下标为 k1k-1kk 的元素得到,越界的情况由突变解决。

在上面的模式中,交换的下标 kk 的序列为(设元素下标从左到右):

3 2 1 {递减到1突变为3}
1 2 3 {递增到3突变为1}
3 2 1 {递减到1突变为3}
1 2 3 {递增到3突变为1}
3 2 1 {递减到1突变为3}
1 2 3

可以看到:对元素个数为 nn 的集合 SS,其交换下标 k,k[1,n1]k, k \in [1,n-1] 的序列有如下规律:

1)开始时 k=n1k = n-1,每次减 11

2)当减到 11 或加到 n1n-1 时,kk 值发生突变:若前一个 k=1k = 1,则变为 n1n-1;若前一个 k=n1k = n-1,则变为 11

3)kk 值突变后,新的 kk 以突变前的 kk 值开始递进(若是 11 就递增,若是 n1n-1 就递减)

4)kk 值突变后的交换下标序列是突变前的序列关于突变位置的“镜像”

比如:前 7 个交换下标 3 2 1 {3} 1 2 3 (加粗的位置为突变位置)
显然,突变位置后的下标 1 2 3 是突变前的下标 3 2 1 的"镜像"

根据如上规律,可编写相应的算法实现

 1import java.util.ArrayList;
 2
 3public class Permutation {
 4
 5    public static void main( String[] args ) {
 6        String[] result = permutation( "12345" );
 7        // System.out.println( result.length + "\r\n" );
 8        for ( String s : result ) {
 9            System.out.println( s );
10        }
11    }
12
13    public static String[] permutation( String str ) {
14
15        ArrayList<String> charList = new ArrayList<String>();
16        char[]            arrChars = str.toCharArray();
17        long              times    = 1;
18        int               k        = arrChars.length - 2;
19        int               inc      = -1;
20
21        for ( int i = 1; i < arrChars.length + 1; i++ ) {
22            times *= i;
23        }
24
25        for ( int i = 1; i < times; i++ ) {
26
27            swap( arrChars, k, k + 1 );
28            charList.add( new String( arrChars ) );
29            k += inc;
30
31            if ( k == -1 ) {
32                inc = 1;
33                k = 0;
34                swap( arrChars, arrChars.length - 2, arrChars.length - 1 );
35                charList.add( new String( arrChars ) );
36                i++;
37            }
38
39            if ( k == arrChars.length - 1 ) {
40                inc = -1;
41                k = arrChars.length - 2;
42                swap( arrChars, 0, 1 );
43                charList.add( new String( arrChars ) );
44                i++;
45            }
46        }
47
48        return charList.toArray( new String[0] );
49    }
50
51    private static void swap( char[] arr, int k1, int k2 ) {
52        char tmp = arr[k1];
53        arr[k1] = arr[k2];
54        arr[k2] = tmp;
55    }
56}
java
 1#include <iostream>
 2#include <string>
 3#include <iterator>
 4#include <algorithm>
 5
 6using namespace std;
 7
 8#define _swap(a, b) { int t = a; a = b; b = t; }
 9
10void permutation(int n) {
11
12	long long times = 1;
13	int *list = new int[n], k = n - 2, maxK = n - 2, dir = -1 ;
14
15	for (long long i = 1; i < n; ++i)
16		times *= i, list[i - 1] = i;
17
18	list[n - 1] = n;
19	// copy(list, list + n, ostream_iterator<int>(cout, " ")), cout << endl;
20
21	for (long long i = 1; i <= times; ++i) {
22		for (int j = 0; j < n - 1; ++j) {
23			_swap(list[k], list[k + 1]);
24			// copy(list, list + n, ostream_iterator<int>(cout, " ")), cout << endl;
25			k += dir;
26		}
27		k = i & 1 ? maxK : 0;
28		_swap(list[k], list[k + 1]);
29		// copy(list, list + n, ostream_iterator<int>(cout, " ")), cout << endl;
30		k = maxK - k;
31		dir = -dir;
32	}
33
34	delete[]list;
35}
36
37int main() {
38	permutation(5);
39}
cpp
  • 实现相同功能的递归实现较多,但时间与空间复杂度高
  • 不使用递归的代码看上去较多一点,但效能收益可观

本文采用 知识共享署名许可协议(CC-BY 4.0)进行许可,转载注明来源即可。如有错误劳烦评论或邮件指出。