字符全排列

题目描述

从n个字符(n从a开始，依次递增)中选取r个字符，对r个字符进行不重复排列。字典序小的在前面。

输入描述

一行，n和r

输出描述

r个字符的所有组合，每种组合占一行，字符和字符之间用空格隔开。

样例输入

1
3 2

样例输出

1
2
3
a b
a c
b c

样例说明

数字3代表c，就是从a,b,c三个中任选两个进行不重复组合。

题目分析

(1)一道搜索与回溯的题目,不同的是要输出不重复的组合
(2)可以直接对字符进行操作
(3)因为题目比较特殊，可以直接对数字排序， 然后由数字转换成字符

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
33
34

#include<iostream>
using namespace std;
int n,r;  //定义一共几个数，需要选几个数 
int pd[100],ans[100];//pd数组是判断是否用过这个数，ans是结果数组 
void print() { //输出函数
    int i;
    for(i=1; i<=r; i++) //根据规模范围输出 
        printf("%c ",ans[i]+'a'-1);//由原来的数字改成字符 
    cout<<endl;
}
void dfs(int k) { //深搜函数，当前是第k格
    int i;
    if(k==r){ //填满了的时候
        print();//输出当前解
        return;
    }
    for(i=ans[k]; i<=n; i++) { //1-n循环填数,先从上一步的数据开始， 
        if(pd[i]==0) { //如果当前数没有用过
            pd[i]=1;//标记一下,1表示当前这个数字使用过 
            ans[k+1]=i;//把这个数填入结果数组
            
            dfs(k+1);//填下一个
            pd[i]=0;//回溯
        }
    }
}
int main() {
    cin>>n>>r;//读入规模和要选几个数 
    ans[0]=1;// 因为要用到上一步的值，所以开始的时候要给初值，不然就会取到0 
    dfs(0);//注意，这里是从第0格开始的！
    return 0;
}