運用窮舉法找出N個數字的所有排列

1. 如何產生N個數字的各種排列

2. 有彈性的迴圈控制

3. 概念簡單的窮舉法 (暴力搜尋)

排列:

解某些問題時你需要一段程式來把所有 n 個整數的所有 n! 排列都找出來, 例如 n = 4, n 個整數集合 {1, 2, 3, 4}, 所有的 24 種排列如下:

		  1, 2, 3, 4				3, 1, 2, 4
		  1, 2, 4, 3				3, 1, 4, 2
		  1, 3, 2, 4				3, 2, 1, 4
		  1, 3, 4, 2				3, 2, 4, 1
		  1, 4, 2, 3				3, 4, 1, 2
		  1, 4, 3, 2				3, 4, 2, 1
		  2, 1, 3, 4				4, 1, 2, 3
		  2, 1, 4, 3				4, 1, 3, 2
		  2, 3, 1, 4				4, 2, 1, 3
		  2, 3, 4, 1				4, 2, 3, 1
		  2, 4, 1, 3				4, 3, 1, 2
		  2, 4, 3, 1				4, 3, 2, 1

使用 n-層 的迴圈來實作:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int i1, i2, i3, i4;

    for (i1=1; i1<=4; i1++)
    {
        for (i2=1; i2<=4; i2++)
        {
            if (i2 == i1) 
                continue;
            for (i3=1; i3<=4; i3++)
            {
                if ((i3==i2)||(i3==i1)) 
                    continue;
                for (i4=1; i4<=4; i4++)
                {
                    if ((i4==i3)||(i4==i2)||(i4==i1)) 
                        continue;
                    printf("%d %d %d %d\n", i1, i2, i3, i4);
                }
            }
        }
    }
    system("pause");
    return 0;
}

注意:

1. 請修改上述程式列出包括集合 {1, 2, 3, 4, 5, 6} 中四個元素的所有排列?
   
   
2. 如果集合中元素很多, 例如 n = 15, 這樣子需要寫很多層的迴圈控制, 這是一個不好的現象, 一般情況下多層的迴圈時內外層迴圈裡的變數很容易互相干擾; 像是一個 Sudoku 的應用程式, 可能有的層數會有 50-70
   
   
3. 如果 n 是由使用者輸入的, 例如 n = 8, n = 3, n = 13, 你可能需要根據可能的最大值寫迴圈, 當 n 小於最大值時跳過內層的迴圈。
   
   
4. 上面程式中迴圈控制變數相當笨拙 i1, i2, ..., i15
   

我們能夠運用陣列來解決上述的問題嗎?

下面這個程式沒有辦法全部解決, 雖然可以增加一點點彈性, 但是程式的複雜度看起來是一樣的, 甚至更難看

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int i[4], j;

    for (i[0]=1; i[0]<=4; i[0]++)
    {
        for (i[1]=1; i[1]<=4; i[1]++)
        {
            if (i[1]==i[0]) 
                continue;
            for (i[2]=1; i[2]<=4; i[2]++)
            {
                for (j=0; j<2; j++)
                    if (i[2]==i[j])
                        j=5;
                if (j>=5) continue;
                for (i[3]=1; i[3]<=4; i[3]++)
                {
                    for (j=0; j<3; j++)
                        if (i[3]==i[j])
                            j=5;
                    if (j>=5) continue;
                    for (j=0; j<3; j++)
                        printf("%d ", i[j]);
                    printf("\n");
                }
            }
        }
    }
    system("pause");
    return 0;
}

可以使用 陣列來存放程式的狀態 並且使用 兩層迴圈 來實作

演算法中資料的變化 (這些資料可以想像成就是前面這個程式裡面陣列 i[0], i[1], i[2], i[3], i[4] 所存放的數值)

達成上面變數變化的程式實作:

1. 使用陣列來存放上面搜尋各種可能性時的狀態 int perm[5];
   
2. 使用變數來記錄上面演算法中黃色方格的位置, 例如 int current;
   
3. 給它一個初始值, 設定在陣列的第一位 current = 0;
   
4. 使用 while 迴圈檢查是否 current >= 0 (這是 "迴圈是否需要繼續下去" 的條件)
   
   4.1 找到 current 位置上 perm[current] 下一個合法的數字 (perm[current] <= 5)
   
   4.2 如果 4.1 找到了, 而且 current<5 , 表示目前在 perm 裡存放的還不是一個完整的排列, current++, 繼續下一位置的列舉
   
   4.3 如果 4.1 找不到, current--, 回到前一個位置上列舉下一個可能的數字
   
   4.4 如果 current == 5, 表示 perm 陣列中已經是一個合法的排列, 列印在螢幕上
   
   步驟 4.1 的細部設計
   
   4.1.1 使用 while 迴圈檢查是否在 current 位置上還有可用的數字, 也就是檢查 perm[current]<5
   
   4.1.1.1 如果還有的話, perm[current]++
   
   4.1.1.2 如果新的數字和左手邊 perm[0], ..., perm[current-1] 數字不重複的話, 就找到了下一個合法的排列
   
   4.1.2 如果上面檢查 perm[current] 由 0 一直到 5 都失敗的話, 就表示必須回到 current-1 位置去看下一個可能性了

程式碼:

    void main()
    {
        int size, perm[12] = {0}, current=0, solCount=0, i;

        printf("Please input number of elements: ");
        scanf("%d", &size);

        while (current>=0)
        {
            current += next(size, current, perm);
            if (current == size)
            {
                solCount++;
                printf("%4d: ", solCount);
                for (i=0; i<size; i++)
                    printf("%d ", perm[i]);
                printf("\n");
                current = size-1;
            }
        }
        printf("Total %d permutations\n", solCount);
    }
  
    int next(int size, int pivot, int perm[])
    {
        int i, collision;

        while (perm[pivot]++ < size)
        {
            collision = 0;
            for (i=0; i<pivot; i++)
                if (perm[pivot] == perm[i])
                {
                    collision = 1;
                    break;
                }
            if (!collision) return 1;
        }
        perm[pivot] = 0;
        return -1;
    }

概念上再簡化一點的程式實作:

我們打算把多層的迴圈換成一個可以調整層數的迴圈, 例如下列 4 層迴圈印出由 1 1 1 1, 1 1 1 2, 到 4 4 4 4 總共 4⁴ 個數列的程式片段:

    int i[4], j;

    for (i[0]=1; i[0]<=4; i[0]++)
    {
        for (i[1]=1; i[1]<=4; i[1]++)
        {
            for (i[2]=1; i[2]<=4; i[2]++)
            {
                for (i[3]=1; i[3]<=4; i[3]++)
                {
                    for (j=0; j<3; j++)
                        printf("%d ", i[j]);
                    printf("\n");
                }
            }
        }
    }

在最裡層的迴圈裡, 可以同時看到陣列 i[] 的內容, 也就是藍字部份列印在螢幕上的數字, 這幾層的迴圈其實最主要的目的就是要在每一種不同的迴圈變數組合下完成列印的工作, 我們可以換成單一迴圈來得到相同的效果:

#include <stdio.h>
#include <stdlib.h>
int next(int perm[], int n);
void printPerm(int perm[], int n);

int main(void)
{
    int n, perm[12];
    printf("請輸入 n 值 > ");
    scanf("%d", &n);
    for (i=0; i<n; i++) perm[i] = 1;

    do 
        printPerm(perm, n);
    while (next(perm, n));

    system("pause");
    return 0;
}

// n 層的迴圈合併成下面這個同時修改 n 個迴圈變數的 向上計數 函式

int next(int perm[], int n)
{
    int i;
    for (i=n-1; i>=0; i--)
        if (perm[i]<n)
        {
            perm[i]++;
            return 1;
        }
        else
            perm[i] = 1;
    return 0;
}

void printPerm(int perm[], int n)
{
    static int count=0;
    int i;
    printf("%d: ", ++count);
    for (i=0; i<n; i++)
        printf("%d ", perm[i]);
    printf("\n");
}

接下來我們加上數字不重複出現的限制就完成了:

do 
    if (isValid(perm, n))
        printPerm(perm, n);
while (next(perm, n));


int isValid(int perm[], int n)
{
    int i, j;
    for (i=0; i<n-1; i++)
        for (j=i+1; j<n; j++)
            if (perm[i]==perm[j])
                return 0;
    return 1;
}

這個程式稍微修改幾列就可以寫出一個 "由 N 個整數中任取 K 個數字的所有排列" 的程式, 再修改一列程式就可以寫出一個 "由 N 個整數中任取 K 個數字的所有組合" 的程式

窮舉法 (暴力搜尋法) 列舉所有可能: 運用 樹狀決策圖 來列舉所有的可能

遞迴版(一):

1. 遞迴函數
   

   void next(int size, int pivot, int perm[])
   {
       int i, collision;
       static int count=0;
   
       perm[pivot] = 0;
       while (perm[pivot]++ < size)
       {
       	collision = 0;
       	for (i=0; i<pivot; i++)
       	    if (perm[pivot] == perm[i])
       	    {
       	        collision = 1;
       	        break;
       	    }
       	if (!collision)
       	{
               if (pivot+1 < size)
                   next(size, pivot+1, perm);
               else
               {
               	printf("%4d: ", ++count);
                   for (i=0; i<size; i++)
                       printf("%d ", perm[i]);
                   printf("\n");
               }
           }
       }
   }

2. main 函數中啟動遞迴函數
   

   void main()
   {
       int size, perm[12] = {0};
       printf("Please input number of elements: ");
       scanf("%d", &size);
       next(size, 0, perm);
   }

遞迴版(二):

1. 遞迴函數
   

   void permutation(int size, int perm[], int pivot, int value, int *nSol)
   {
       int i;
   
       if (collision(pivot-1, perm, value))
           return;
   
       perm[pivot] = value;
       if (pivot==size)
       {
           ++(*nSol);
           if (*nSol % 100000 == 0)
               printf(".");
           if (size<=6)
               printPerm(*nSol, size, perm);
           return;
       }
   
       for (i=0; i<size; i++)
           permutation(size, perm, pivot+1, i+1, nSol);
   
       return;
   }

2. 輔助函數
   

   void printPerm(int iSol, int size, int *perm)
   {
       int i;
       printf("%d:", iSol);
       for (i=1; i<=size; i++)
           printf("%3d", perm[i]);
       printf("\n");
   }
   
   int collision(int pivot, int *perm, int value)
   {
       int i;
       for (i=1; i<=pivot; i++)
           if (perm[i] == value)
               return 1;
       return 0;
   }

3. main 函數
   

   void main()
   {
       int i, size, nSol=0;
       int *perm;
   
       do
       {
           printf("Please input N (N>=3): ");
           scanf("%d", &size);
       }
       while (size<3);
   
       perm = (int *) malloc((size+1)*sizeof(int));
       for (i=0; i<=size; i++)
           perm[i] = 0;
       
       permutation(size, perm, 0, 0, &nSol);
       printf("\n# of solutions = %d\n", nSol);
   
       free(perm);
   }