假設數組含有n個元素，則提取數組中的每一個元素做一次頭元素，然後全排列除數組中除第一個元素之外的所有元素，這樣就達到了對數組中所有元素進行全排列的得目的。【這句話才是重點！】 比如 1，2，3.的全排列就是分別以1，2，3開始的全排列。 以1開始的全排列也就是2，3.的全排列，（2，3）的全排列就是分別以2和3開始的全排列。 設全排列R(n1,n2,n3.....nn)，可以化簡為分別以n1,n2,n3……開始的全排列。 即 n1R1(n2,n3.....nn)，n2R2(n1,n3.....nn)，n3R3(n1,n2,.....nn)……nnR(n1,n2,n3.....) 其中，R1(n2,n3.....nn)又可以按照R的方式繼續進行……以此類推可以得到全排列。 復制代碼 #include<iostream> using namespace std; //index，代表遞歸過程中，子數列在原始數列中的位置 //例如 a[] = {1,2,3},原始數列長度LENGTH = 3， //遞歸到其中某一步時index = 1，num= 2，代表要從原始數列的下表為1處，長度為2(即自數列2，3)開始，查找子數列 //(2,3)的全排列 //LENGTH 為原始數組的長度，這個是不會變的。 void permutation(int values[], int index, int num,int LENGTH) { int i = 0; if(num == 0)//已經找到一個全排列，顯示輸出 { for(i=0; i<LENGTH;++i) { cout<<values[i]<<" "; } cout<<endl; return; } for(i=0; i<num; i++) { swap(values[index+i], values[index]);//第index個整數和第index+i個數字交換，保證自數列的第一個元素與該子數列中每一個元素進行一次交換，進行排列。 permutation(values, index+1, num-1);//對從index+1到數組最末端的元素進行全排列 swap(values[index], values[index+i]);//for循環中第一條語句的逆操作，其目的是使數組倒回原來的樣子， //這樣做的目的是使排列不會產生重復的結果。 } return; } int main() { int values[]={1，3，5}; permutation(values,0,3,3); cout<<endl<<endl; for(int i=0;i<3;++i) { cout<<values[i]<<' '; } cout<<endl<<endl; return 0; } 復制代碼
