擅长排列的小明

我不是女神ヾ 2022-08-01 00:25 176阅读 0赞

## 擅长排列的小明 ##

时间限制： 1000 ms  |  内存限制： 65535 KB

难度： 4

描述

小明十分聪明，而且十分擅长排列计算。比如给小明一个数字5，他能立刻给出1-5按字典序的全排列，如果你想为难他，在这5个数字中选出几个数字让他继续全排列，那么你就错了，他同样的很擅长。现在需要你写一个程序来验证擅长排列的小明到底对不对。

输入

第一行输入整数N（1<N<10）表示多少组测试数据，  
每组测试数据第一行两个整数 n m (1<n<9,0<m<=n)

输出

在1-n中选取m个字符进行全排列，按字典序全部输出,每种排列占一行，每组数据间不需分界。如样例

样例输入

2
    3 1
    4 2

样例输出

1
    2
    3
    12
    13
    14
    21
    23
    24
    31
    32
    34
    41
    42
    43

来源

[\[hzyqazasdf\]原创][hzyqazasdf]

上传者

[hzyqazasdf][hzyqazasdf 1]

**上面那一题是用C++ stl写的，看到数据有点小就想到用dfs，果**

**然好使！因为原来做过这样的题目，所以轻松了很多。这一题跟**

**那一题最大的区别就是这一题无论p到哪里了，都必须拐回到开**

**始搜索，特别棒！**

#include<cstdio>
    #include<cstring>
    #include<iostream>
    using namespace std;
    int isv[10];
    int ring[10];
    int n,m,flag;
    void dfs(int p,int num)
    {
        int i;
        if(num==0)
        {
            for(i=flag;i>=1;i--)
            {
                cout<<ring[i];
            }
            cout<<endl;
        }
        else
        {
            for(i=p;i<=n;i++)
            {
                if(!isv[i])
                {
                    isv[i]=1;
                    ring[num]=i;
                    dfs(1,num-1);
                    isv[i]=0;
                }
            }
        }
    }
    int main()
    {
        int t;
        cin>>t;
        while(t--)
        {
            cin>>n>>m;
            flag=m;
            memset(isv,0,sizeof(isv));
            dfs(1,m);
        }
    }

[hzyqazasdf]: http://acm.nyist.net/JudgeOnline/search_result.php?source=%5Bhzyqazasdf%5D%E5%8E%9F%E5%88%9B
[hzyqazasdf 1]: http://acm.nyist.net/JudgeOnline/profile.php?userid=hzyqazasdf