運用旋轉法產生 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

你也需要特別注意到上面這個列表很容易造成誤會, 讓你以為需要寫迴圈直接 4 個數字一起轉, 轉一次輸出一次, 然後在兩段的中間才考慮前 3 個一起轉, 轉 3 次以後再考慮轉前 2 個, 這樣子的想法程式架構會變成：

for (i2=0; i2<2; i2++) // 前 2 個轉, 轉 2 次
{
    for (i3=0; i3<3; i3++) // 前 3 個轉, 轉 3 次
    {
        for (i4=0; i4<4; i4++) // 前 4 個轉, 轉 4 次
        {
            1. 列印目前陣列內容
            2. 旋轉前 4 個元素
        }
        旋轉前 3 個元素
    }
    旋轉前 2 個元素
}

總計列印 4*3*2 = 24 種不同的排列, 好像合理喔, 但是程式這樣寫就限制為 4 個元素的排列了, 要改成 5 個, 6 個, 7 個的時候要改寫程式或是想辦法跳過一些內部迴圈, 恐怕不是好的想法。

上面這些輸出的列表, 你可能需要把程式想成

while (there are more permutation)
{
    列印目前陣列內容
    轉 前n個, 前n-1個, ...., 前2個 元素 
}

資料表示方法:

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

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

旋轉右移:

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

void rotate(int x[], int size)
{
    int i;
    int 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 就表示沒有其它排列了

int rotate_n_check(...)
{
    int i;
    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 頁)。

如果同學還是覺得運用函式撰寫使你的思考沒有辦法連貫，基本上應該是還不習慣運用函式來簡化你的構思與組織，也可以參考下面兩個沒有運用函式的版本，程式是完整的，可以編譯測試，但是排列順序調整了一下，並不是可以直接上傳的程式，基本邏輯還是和上面的相同：

#include <stdio.h>

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

int main()
{
    int i=2, n=4, data[]={0,1,2,3};
    while (i>1)
    {
        for (i=0; i<n; i++)
            printf("%d%c", data[i], i<n-1?' ':'\n');
        for (i=n; i>=2; i--)
        {
            rotate(data, i);
            if (data[i-1] != i-1) break;
        }
    }
    return 0;
}

#include <stdio.h>

int main()
{
    int i=2, j, t, n=4, data[]={0,1,2,3};

    while (i>1)
    {
        for (i=0; i<n; i++)
            printf("%d%c", data[i], i<n-1?' ':'\n');
        for (i=n; i>=2; i--)
        {
            t = data[0];
            for (j=0; j<i-1; j++)
                data[j] = data[j+1];
            data[i-1] = t;
            if (data[i-1] != i-1) break;
        }
    }
    return 0;
}

1111-1C 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

範例執行程式

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