Koi

递归实现n个不同字符的全排列

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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);
}