NOIP2012普及组初赛 完善程序 第2题《排列数》

Keywords: DFS，爆搜

#include <cstring>
#include <iostream>

using namespace std;

const int N = 25;

bool used[N];
int data[N];
int n, m ,i, j, k;
bool flag;

int main()
{
    cin >> n >> m;
    memset(used, false, sizeof used);

    for (i = 1; i <= m; i++) //取第一种方案 
        data[i] = i, used[i] = true;

    flag = true;
    while (flag)
    {
        for (i = 1; i <= m - 1; i++) cout << data[i] << ' ';
        cout << data[m] << endl;   //输出当前方案 

        flag = false;  //1空 
        for (i = m; i >= 1; i--)  //从后往前找能变大的数 
        {
            used[data[i]] = false; //2空   //相当于把箱子腾空 
            //每次到这找到第一个能变大的数字，然后变大
            for (j = data[i] + 1; j <= n; j++)
                if (!used[j])
                {
                    used[j] = true;
                    data[i] = j;  //3空  //找到能变大的数字，就存在data[i]的位置上 
                    flag = true;  //找到一组新方案 
                    break; //找到后跳出for  
                }

            if (flag)  //当找到的时候 
            {
                //接着把i后面的数字直接从小到大安排，形成新的方案
                //i后面的数字没被用过的，就放进来 
                for (k = i + 1; k <= m; k++)
                    for (j = 1; j <= n; j++)  //从小到大找一遍 
                        if (!used[j])
                        {
                            data[k] = j;
                            used[j] = true;
                            break;
                        }
                break;//5空  找到一组新的方案后，跳回while，输出新的方案 
            }
        }
    }

    return 0;
}