当前位置：首页 > 题解目录 > 正文内容

字符全排列(2)

亿万年的星光4年前 (2021-01-28)题解目录1621

【题目描述】

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

【输入描述】

一行，n和r

【输出描述】

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

【样例输入】

3 2

【样例输出】

a b
a c
b c

【样例说明】

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

【题目分析】

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

【参考代码1】

#include<bits/stdc++.h>
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;
}