運用旋轉法產生 n 個整數的所有排列

1. 練習實作迭代式 (iterative) 的演算法 (練習迴圈控制)

2. 這個演算法和我們平常產生排列的方式有一些差異, 不過用迴圈寫起來比較簡潔!

n 個整數有 n! 種排列方式:

n = 3, n! = 3 * 2 = 6

六種排列如下:

0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

程式實作

上面是大部分人列出這六種排列的順序, 我們可以用遞迴的方式來描述這個演算法:

1. 固定第一個元素為 0, 排列剩下的兩個元素 {1, 2}
2. 固定第一個元素為 1, 排列剩下的兩個元素 {0, 2}
3. 固定第一個元素為 2, 排列剩下的兩個元素 {0, 1}

參考 運用窮舉法找出 n 個整數的所有排列, 也可以用數數字的方式來描述這個演算法:

1. 把三個數字看成是 3 進位的三位數數字
2. 由 0 0 0 開始往上數, 跳過所有有重複數字的, 0 0 1, 0 0 2, 0 1 0, 0 1 1, 0 1 2
3. 0 2 1, 0 2 2, 1 0 0, 1 0 1, 1 0 2, 1 1 0, ..., 1 2 0, 1 2 1, 1 2 2, 2 0 0, 2 0 1, 2 0 2, 2 1 0, ..., 2 2 2

其實產生這個順序的演算法, 不管是疊代式 (iterative) 的程式或是遞迴式 (recursive) 的程式, 寫起來都有一定的複雜度, 希望透過這個練習讓大家更能夠掌握迴圈、陣列、以及函數。

以下我們來看一個特別的 "旋轉法" 的範例:

考慮 n = 4, n! = 24。所有的 24 種排列, 以及每一個動作詳細的說明如下:

0 1 2 3   <-- 起始狀態
3 0 1 2   <-- 4 個數字一起向右旋轉,轉出去的再由左邊進來
2 3 0 1   <--                 "
1 2 3 0   <--                 "
0 1 2 3       旋轉 4 次以後 "3" 回到它的初始位置, 
                            需要將前 3 個數字向右旋轉
2 0 1 3   <-- 由於元素 "2" 不在原來的位置上, 我們得到一個新的排列
3 2 0 1   <-- 4 個數字一起向右旋轉,轉出去的再由左邊進來
1 3 2 0   <--                 "
0 1 3 2   <--                 "
2 0 1 3       旋轉 4 次以後 "3" 回到它的初始位置, 
                            需要將前 3 個數字向右旋轉
1 2 0 3   <-- 由於元素 "2" 不在原來的位置上, 我們得到一個新的排列
3 1 2 0   <-- 4 個數字一起向右旋轉,轉出去的再由左邊進來
0 3 1 2   <--                 "
2 0 3 1   <--                 "
1 2 0 3       旋轉 4 次以後 "3" 回到它的初始位置, 
0 1 2 3                需要將前 3 個數字向右旋轉, 此時 "2" 回到它的初始位置,
1 0 2 3   <--  需要將前 2 個數字向右旋轉,
                            由於元素 "1" 不在原來的位置上, 我們得到一個新的排列
3 1 0 2   <-- 4 個數字一起向右旋轉,轉出去的再由左邊進來
2 3 1 0   <--                 "
0 2 3 1   <--                 "
1 0 2 3       旋轉 4 次以後 "3" 回到它的初始位置, 
                             需要將前 3 個數字向右旋轉,
2 1 0 3   <-- 由於元素 "2" 不在原來的位置上, 我們得到一個新的排列
3 2 1 0   <-- 4 個數字一起向右旋轉,轉出去的再由左邊進來
0 3 2 1   <--                 "
1 0 3 2   <--                 "
2 1 0 3       旋轉 4 次以後 "3" 回到它的初始位置,
0 2 1 3                    需要將前 3 個數字向右旋轉,
0 2 1 3   <-- 由於元素 "2" 不在原來的位置上, 我們得到一個新的排列
3 0 2 1   <-- 4 個數字一起向右旋轉,轉出去的再由左邊進來
1 3 0 2   <--                 "
2 1 3 0   <--                 "

0 2 1 3   <-- 旋轉 4 次以後 "3" 回到它的初始位置,
                           需要將前 3 個數字向右旋轉,
1 0 2 3       由於元素 "2" 回到它的初始位置,
                           需要將前 2 個數字向右旋轉,
0 1 2 3       由於元素 "1" 回到它的初始位置,
                  沒有可以旋轉的了, 程式結束

大部分人都不會用這樣的方法來列出所有的排列, 但是接下來我們會看到這個演算法轉換成疊代式的程式, 非常簡潔。

Sample execution program

資料表示方法:

將集合 {0, 1, 2, ..., n-1} 中的元素放進一個陣列

#include <stdio.h>
...
int i, n;
char data[10];
...
printf("Please input n :");
scanf("%d", &n);
for (i=0; i<n; i++)
    data[i] = i;

旋轉右移:

在上面演算法中我們需要不斷把不同大小的陣列向右移動並轉入左側 (如下圖), 所以我們寫一個函數來得到這個功能:

void rotate(char x[], int size)
{
    int i;
    char tmp = x[size-1];
    for (i=size-1; i>0; i--)
        x[i] = x[i-1];
    x[0] = tmp;
}

旋轉並且檢查:

這個演算法裡面最關鍵的步驟其實就是這個:

2 1 3 0 (四個一起轉)
0 2 1 3 (發現3回到data[3],前三個一起轉)
1 0 2 3 (發現2回到data[2],前兩個一起轉)
0 1 2 3 (發現1回到data[1],已經沒有其他排列了,結束)

有的時候會有一點沒辦法掌握為什麼要連續這樣子轉, 我們可以舉一個類似的例子給你一些直覺, 假設我們由 0000 一直數到 9999, 當數到 0009 再往下數時你需要進位成 0010, 當數到 0099 再往下數時你需要連續兩次進位成 0100, 當數到 0999 再往下數時你需要連續三次進位成 1000, 上面旋轉法裡面 數字 i 回到 data[i] 就類似已經數到 9 需要進位的狀況, 要一直進位到不是 9 的時候才停止 (更仔細去思考這個演算法, 我們需要證明它可以找到所有的排列)

rotate(data, 4);
if (data[3] == 3)
{
    rotate(data, 3);
    if (data[2] == 2)
    {
        ...
    }
}

上面直接把關鍵步驟的動作寫成程式, 不過這樣子寫的話, 會有三層的巢狀 if 敘述, 而且 n 就固定為 4 了, n 如果要改成 5 的話, 要增加一層的 if, 需要重新編譯程式; 如果 n 的數值是由執行程式的人輸入的話, 程式需要稍微修改; 首先可以看到重複的 rotate(data, i); if (data[i-1]==i-1) 這樣的兩個敘述, 差別只有在 i 的數值, 前面我們看過這樣是運用迴圈語法的好時機, 只是會覺得 if () 檢查成功時要進行的動作好像不知道該放在哪裡, 你可以把它想成: if 檢查成功時就要繼續下一次的 rotate(), 等於說 if 的檢查內容其實可以和迴圈繼續執行的條件結合起來, 類似

for (i=4; i>=2 && data[i]!=i; i--)
    rotate(data, i);

重複旋轉並且檢查:

我們把這段程式寫在一個 rotate_n_check 函數裡, 函數回傳 1 就表示找到一個新的起始排列, 可以繼續旋轉, 函數回傳 0 就表示沒有其它排列了

for (i=n; i>=2; i--)
{
    rotate(data, i);
    if (data[i-1] != i-1) return 1;
}
return 0;

每個人在處理這樣的邏輯時方法都會有很大差異, 你應該要試著自己用程式碼寫出你想要完成的, 再來比對上面的程式碼, 看看有什麼地方是不一樣的, 比較一下好處與壞處, 這樣子的學習效果會比較大

main() 函數以及輸出結果的輔助函數:

運用前一個步驟的 rotate_n_check() 函數, 在 main() 函數中可以用一個簡單的 while 迴圈來完成整個演算法。

do
    printPermutation(data, n);
while (rotate_n_check(data, n));

printPermutation() 中只是一個單純的 printf() 迴圈如下:

for (i=0; i<n-1; i++)
    printf("%d ", data[i]);
printf("%d\n", data[n-1]);

上面這個程式你可以和 窮舉法找出所有排列 的程式相比較, 應該可以看出來 rotate_n_check() 這個函數就像是 next() 函數, 目的在產生下一個合法的排列, 只是這裡 "下一個" 的定義比較特別一點。

e-Tutor 線上繳交

我們現在有了一個產生 n! 種排列的迭代式演算法, 請修改一下, 運用旋轉法產生有條件限制的排列:

以 n = 4, k=2 為例, 排列 0 1 2 3 中任意兩個數字 a, b 都是符合由小到大順序的 (滿足 a < b), 排列 2 1 0 3 中則有三組數字反序 (不滿足 a < b), 亦即 2 > 1, 2 > 0, 1 > 0, 請輸出所有具有 2 的倍數組反序數字的排列, 例如

0 1 2 3 (0 次)
2 3 0 1 (4 次)
2 0 1 3 (2 次)
1 3 2 0
1 2 0 3
0 3 1 2
3 1 0 2
0 2 3 1
3 2 1 0
1 0 3 2
3 0 2 1
2 1 3 0

範例執行程式

完成以後, 請線上繳交 原始程式檔案