運用旋轉法產生 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 個整數的所有排列, 其實產生這個順序的演算法, 不管是疊代式 (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" 回到它的初始位置,
                             需要將前 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;
}

旋轉並且檢查:

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

基本上這是關鍵步驟的程式, 可以用來產生一組排列 (注意這一個動作包含了好幾個檢查); 不過這樣子寫的話, n 就固定為 4 了, 如果 n 的數值是由執行程式的人輸入的話, 程式需要再稍微修改一下

重複旋轉並且檢查:

我們把這段程式寫在一個 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; i++)
    printf("%d ", data[i]);
printf("\n");

上面這個程式你可以和 窮舉法找出所有排列 的程式相比較, 應該可以看出來 rotate_n_check() 這個函數就像是 next() 函數, 目的在產生下一個合法的排列, 只是這裡 "下一個" 的定義比較特別一點。當然也需要證明一下這個方法真的可以找到所有的 n! 種排列 (參考第 23 頁)。

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, 請輸出所有「逆序對」組數為 k=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

範例執行程式

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