Description

设str是含有n个不同字符的数组，perm(str,k-1,n)为str[0]~str[k-1]的所有字符的全排列。很明显，perm(str,k-1,n)处理的字符个数比perm(str,k,n)处理的字符个数少一个。

假定perm(str,k-1,n)可求，str[k]位置可以任取str[0]~str[k]的任何值，再组合perm(str,k-1,n)得到perm(str,k,n)。

Algorithm

{% codeblock lang:c %} #include <stdio.h>

void perm(char str[], int k, int n) {
    int i, j;
    if (k == 0)
    {
        for (j = 0; j < n; j++)
            putchar(str[j]);
        putchar('\n');
    }
    else
    {
        for (i = 0; i <= k; i++)
        {
            int temp;
            temp = str[k];
            str[k] = str[i];
            str[i] = temp;		//任取小于等于k的i与k交换  
            perm(str, k - 1, n);
            temp = str[k];
            str[k] = str[i];
            str[i] = temp;		//还原以得到原始数组，下次再任取  
        }
    }
}

int main(void)
{
    char str[3] = { 'a','b','c' };
    int n = 3;
    perm(str, 2, 3);
}

{% endcodeblock %}