1.背景

排列和组合是组合数学中的基本算法。求排列组合的计数有现成的公式，P(n,r)=(n!)/((n-r)!),C(n,r)=P(n,r)/(r!)。在利用排列组合求解计数问题的时候，可以直接应用公式。但有时我们需要枚举出排列或组合的每一个元组。本篇只考虑枚举排列算法，且只考虑全排列。待给出枚举组合算法后，通过组合算法和全排列算法，可以容易得出枚举任意排列的算法。

枚举排列的每一个元组有很多种方法，下面介绍一种方法：

2.算法思想（以4元素排列为例）

把组成排列的每个元素从小到大排列，这当作排列的第一个元组。把组成排列的每个元素从大到小排列，这当作排列的最后一个元组。构造规则，使元组按规律递增构造出中间的元组。

0，1，2，3
0，1，3，2
0，2，1，3
……
3，2，1，0

3.算法步骤

（1）把组成排列的每个元素从小到大排列，这当作排列的第一个元组。
（2）从后向前搜索当前元组中的元素，发现第一个位置，此位置相邻后面的元素大于前面的元素。
（3）搜索此位置后的元素，找到大于此位置元素最小的那个，交换两个元素。
（4）交换后，将此位置后的元素从小到大排列。得到一个元组。
（5）重复（2）-（5）步骤，直到第（2）步中没有发现这样的位置。

4.算法代码

#include <stdio.h>
#define MAX 100

void OutputPermutation(int ary[],int n)
...{
    static int count=0;
    int i;
    printf("%05d : ",++count);
    for(i=0;i<n;i++)
    ...{        
        printf("%d ",ary[i]);
    }
    printf("/n
");
}

//choose sort
void sort(int ary[],int beginIdx,int endIdx)
...{
    int i,k,tmp,min;
    for (i=beginIdx;i<=endIdx;i++)
    ...{
        min=i;
        for(k=i+1;k<=endIdx;k++)
        ...{
            if(ary[k]<ary[min]) min=k;
        }
        if(min!=i)
        ...{
            tmp=ary[i];
            ary[i]=ary[min];
            ary[min]=tmp;
        }
    }
}

//complete permutation of n tuples
void P_Complete(int n)
...{
    int i,outer,inner,tmp,min;
    int ary[MAX];
    bool finished;
    for(i=0;i<n;i++) ...{ary[i]=i;}
    //output first permutation
    OutputPermutation(ary,n);

    finished=false;
    while(!finished)
    ...{
        finished=true;
        for(outer=n-2;outer>=0;outer--)
        ...{            
            if(ary[outer]<ary[outer+1])
            ...{    
                min=outer+1;
                for(inner=outer+1;inner<=n-1;inner++)
                ...{
                    if(ary[min]>ary[inner] && ary[outer]<ary[inner])
                    ...{
                        min=inner;
                    }
                }
                tmp=ary[outer];
                ary[outer]=ary[min];
                ary[min]=tmp;
                sort(ary,outer+1,n-1);
                //Output permutation
                OutputPermutation(ary,n);
                finished=false;
                break;
            }        
        }        
    }
}

void permutation_test()
...{
    P_Complete(4);
}

int main()
...{
    permutation_test();
}

5.运行结果

6.例子

6.1问题描述

n皇后问题。在n×n棋盘上放置n个皇后，使她们不会互相攻击。

6.2算法描述

我们用row[n]=m表示在棋盘的第n行的m列放置皇后。
我们用n的全排列枚举棋盘上摆皇后所有的可能。
验证摆法是否满足条件，使皇后不会互相攻击。

我们表示棋盘的方法保证了棋盘上每一行只会有一个皇后。我们枚举的每一个方案都是n的全排列的元组，保证了棋盘上每一列只会有一个皇后。我们验证皇后不会互相攻击，只需要验证对角线方向不会有多余一个皇后就可以了。

6.3代码

#include <stdio.h>

#define MAX 100

//output chess board
void OutBoard(int row[],int n)
...{
    int k,i;
    printf("/n
");
    for (i=0;i<n;i++)
    ...{
        for(k=0;k<n;k++)
        ...{
            if(row[i]==k)
                printf("* ");
            else
                printf("@ ");
        }
        printf("/n
");
    }
    printf("/n
");
}

//check if queens will attack each other
bool IsInterAttack(int row[],int n)
...{
    int i,k;
    for(i=0;i<n;i++)
    ...{
        for(k=0;k<n;k++)
        ...{
            if(k==i) continue;
            //check column
            //if(row[i] == row[k]) return true;
            //check slash diagonal direction
            if(i+row[i] == row[k] + k) return true;
            //check back slash diagonal direction
            if(i-row[i] == k-row[k]) return true;
        }
    }
    return false;
}


void OutputPermutation(int ary[],int n)
...{
    static int count=0;
    if(    !IsInterAttack(ary,n) )
    ...{
        printf("count:%d
",++count);
        OutBoard(ary,n);
    }
}

//choose sort
void sort(int ary[],int beginIdx,int endIdx)
...{
    int i,k,tmp,min;
    for (i=beginIdx;i<=endIdx;i++)
    ...{
        min=i;
        for(k=i+1;k<=endIdx;k++)
        ...{
            if(ary[k]<ary[min]) min=k;
        }
        if(min!=i)
        ...{
            tmp=ary[i];
            ary[i]=ary[min];
            ary[min]=tmp;
        }
    }
}

//complete permutation of n tuples
void P_Complete(int n)
...{
    int i,outer,inner,tmp,min;
    int ary[MAX];
    bool finished;
    for(i=0;i<n;i++) ...{ary[i]=i;}
    //output first permutation
    OutputPermutation(ary,n);

    finished=false;
    while(!finished)
    ...{
        finished=true;
        for(outer=n-2;outer>=0;outer--)
        ...{            
            if(ary[outer]<ary[outer+1])
            ...{    
                min=outer+1;
                for(inner=outer+1;inner<=n-1;inner++)
                ...{
                    if(ary[min]>ary[inner] && ary[outer]<ary[inner])
                    ...{
                        min=inner;
                    }
                }
                tmp=ary[outer];
                ary[outer]=ary[min];
                ary[min]=tmp;
                sort(ary,outer+1,n-1);
                //Output permutation
                OutputPermutation(ary,n);
                finished=false;
                break;
            }        
        }        
    }
}

int main(int argc, char* argv[])
...{
    P_Complete(4);
    return 0;
}

6.4运行结果

7.进一步思考

在网上看到一个网友的另一种枚举排列的非递归方法，觉得值得记录下来。他的算法的思想是（以4元组排列为例）：
（1）以0，0，0，0初始化元组。
（2）把4元组看成4进制的数字，从低位不断进行加1操作，逢4进1。
（3）重复（2）当元组中4个数字互不相同时，输出一个元组。
（4）重复（2）-（3）直到元组为3，2，1，0。

在上一篇枚举法解决4皇后问题的例子中，采取的方法是很笨的，而且不易于扩展。本篇利用枚举排列中元组的方法，同是枚举法，扩展性提高了。现在扩展到可以解决n皇后的问题。用枚举法解决n皇后问题始终不是最通常的解法，最通常的解法是回溯法。

[采用CSDN编辑器Copy/Paste代码时，经常会把/n符号弄丢，printf("/n")就变为了printf(" ")不知何故。]