全排列算法实现

问题

得到a，b，c，d的所有排列顺序。

思想

分治法：依次固定第一位的字母，剩下的位再做全排列。

例如，

// Q(a,b,c,d)表示a,b,c,d的全排列
Q(a,b,c,d) = {
    1=a,+Q(b,c,d),	// 第一位是a，剩下bcd做全排列
	1=b,+Q(a,c,d),	// ab交换,使b做第一位
	1=c,+Q(b,a,d),	// ac交换,使c做第一位
	1=d,+Q(b,c,a),	// ad交换,使d做第一位
}

这样4字母的全排列就被分解成了多个3字母全排列，如此继续递归，最终一个字母的全排列就是它本身，递归结束。

代码

#include<iostream>
using namespace std;

//交换
void swap (char &a, char &b) {
	char temp;
	temp = a;
	a = b;
	b = temp;
}

//全排列递归算法
void permutation (char list[], int first ,int size) {
	if (first == size - 1) {
		for (int i = 0 ;i < size; i++) {
            cout << list[i];
        } 
		cout << endl; 
	} else {
	 	for (int i = first; i < size; i++) {
	 		swap(list[i],list[first]);
	 		permutation(list, first + 1, size);
	 		swap(list[i], list[first]);
		}
	}
}

int main (void) {
   char list[] = {'a', 'b', 'c', 'd'};
   int first = 0;
   int size = 4;
   permutation(list, first, size);
}

结果

abcd
abdc
acbd
acdb
adcb
adbc
bacd
badc
bcad
bcda
bdca
bdac
cbad
cbda
cabd
cadb
cdab
cdba
dbca
dbac
dcba
dcab
dacb
dabc