By SmartPtr(http://www.shnenglu.com/SmartPtr/)
給出1， 2， 3， 4四個數， 請編程輸出其全排列， 如：
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
...
這樣的題， 我們在學校的時候一般都遇到過，而我們最先能想到的，應該就是遞歸實現了，因為這和我們我理解的數學中的排列組合比較一致：先取第一個數，有4種可能，再在剩下的3個數種取出第二個數，這又有3種可能，這樣下去直到取到最后一個數。 這樣，4個數的全排列就有4*3*2 = 24個。n個數的全排列就是n*(n-1)*(n-2)*...*2*1. 按照這個描述， 我們發現有兩點在程序中遞歸實現時十分重要：
1. 哪些數已經取過了而哪些數又是沒有取過，可以用的?
2. 現在取的是哪一個數。
確保了這兩個信息，我們的遞歸實現就沒有什么問題了。對于第一個問題，我們有兩種方法可以實現：
1） 用一個對應的bool型數組來記錄被排列數組的使用狀態，這個狀態在遞歸過程中需要回溯
2） 用一個ILLEGAL值來表示不是屬于排序的數，排列數組中的數一旦被使用，就用這個值來覆蓋，當然，遞歸過程中此值也需要回溯。
同樣，現在取得是哪個數，我們也有兩種方法來表示：
1） 用參數的方式來表明這次遞歸調用是為了得第幾個值、
2） 用一個靜態變量來表示當前遞歸的深度，此深度值表明了我當前取的是哪個數。
上面兩點的兩種解決方法排列組合一下:),我們就有4種方法
首先是定義最大數組長度與非法值
#define N 10
#define ILLEAGALNUM -100
下面列出每一種實現：
//數組存使用狀態，調用深度表示取第幾個數
void Permutation1(int a[], int n)
{
static int out[N]; // result array
static bool m[N] = {1,1,1,1,1,1,1,1,1,1}; // mark array, indicate whether the coorespond element
//in array a is already used.
static int depth = -1; //recursive call depth.
depth++;
for(int i = 0; i < n; ++i)
{
if(depth == n) // if we already get the last num, print it
{
static int l = 1;
printf("%3d: ", l++);
for(int k = 0; k<n; k++) printf("%d ", out[k]);
printf(" ");
depth--;
return;
}
else if(true == m[i]) // if element i not used
{
out[depth] = a[i];
m[i] = false; // mark element i as used
Permutation1(a, n); // recursive to get next num
m[i] = true; // backdate , so that we can try another case
}
}
depth--;
}
//修改數據數組表示其使用狀態，參數表示取第幾個數
void Permutation2(int a[], int index, int n)
{
static int out[N];
for(int i = 0; i < n; ++i)
{
if(index == n) //index > n-1, try to get the n-1 num, means it is ok , printf it
{
static int l = 1;
printf("%3d: ", l++);
for(int k = 0; k<n; k++) printf("%d ", out[k]);
printf(" ");
return;
}
else if(a[i] != ILLEAGALNUM)
{
out[index] = a[i];
a[i] = ILLEAGALNUM;
Permutation2(a, index+1, n);
a[i] = out[index];
}
}
}
//修改數據數組表示其使用狀態，調用深度表示取第幾個數
void Permutation3(int a[], int n)
{
static int out[N];
static int depth = -1; //recursive call depth.
depth++;
for(int i = 0; i < n; ++i)
{
if(depth == n) //index > n-1, try to get the n-1 num, means it is ok , printf it
{
static int l = 1;
printf("%3d: ", l++);
for(int k = 0; k<n; k++) printf("%d ", out[k]);
printf(" ");
depth--;
return;
}
else if(a[i] != ILLEAGALNUM)
{
out[depth] = a[i];
a[i] = ILLEAGALNUM;
Permutation3(a, n);
a[i] = out[depth];
}
}
depth--;
}
//額外的數組表示其使用狀態，參數表示取第幾個數
void Permutation4(int a[], int index, int n)
{
static int out[N]; // result array
static bool m[N] = {1,1,1,1,1,1,1,1,1,1}; // mark array, indicate whether the coorespond element
//in array a is already used.
for(int i = 0; i < n; ++i)
{
if(index == n) // if we already get the last num, print it
{
static int l = 1;
printf("%3d: ", l++);
for(int k = 0; k<n; k++) printf("%d ", out[k]);
printf(" ");
return;
}
else if(true == m[i]) // if element i not used
{
out[index] = a[i];
m[i] = false; // mark element i as used
Permutation4(a, index+1, n); // recursive to get next num
m[i] = true; // backdate , so that we can try another case
}
}
}
雖然對于這樣的問題效率與空間相差不會特別明顯，但是我們還是來比較一下來找出最佳的一個。對于數組使用狀態的保存，顯然，用第一個方案需要動用一個額外的數組，而并沒有提高效率，所以我們應該采用第二個方案：修改數組值的方法。對于當前取的是哪個數，如果我們用傳參數的方式，因為在排列過程中，這個遞歸函數被調用的次數是非常多的。（6個數的全排列就要調用1957次），這樣多一個參數， 其每次調用壓棧出棧的消耗就顯得比較大了， 所以我們推薦用調用深度來表示。
經過上面的討論， Permutation3就是我們的最佳選擇。
posted on 2007-08-26 20:45
SmartPtr 閱讀(797)
評論(0) 編輯 收藏 引用