排列枚举

例题:生成排列

For example, the permutations of {0,1,2} are (0,1,2), (0,2,1), (1,0,2), (1,2,0), (2,0,1) and (2,1,0).

// Each function call adds a new element to permutation. 
// The array chosen indicates which elements are already included in the permutation.
// If the size of permutation equals the size of the set, a permutation has been generated.
void search() {
    if (permutation.size() == n) {
       // process permutation
        return ;
    }
    for (int i = 0; i < n; i++) {
        if (chosen[i]) continue;
        chosen[i] = true;
        permutation.push_back(i);
        search();
        chosen[i] = false;
        permutation.pop_back();
    }
}
search(); //调用

// The C++ standard library contains the function next_permutation 
// that can be used for this
vector<int> permutation;
for (int i = 0; i < n; i++) {
    permutation.push_back(i);
}
do {
    // process permutation
} while (next_permutation(permutation.begin(),permutation.end()));

例题:递归实现排列型枚举

排列枚举

//用数组存方案
//注意一下 0-index，如果是 1-index 呢？递归的边界是....什么？(提问)
void dfs(int k)
{
    if (k == n)
    {
        for (int i = 0; i < n; i++)
            cout << order[i] << ' ';
        puts("");
    }
    for (int i = 1; i <= n; i++)
    {
        if (chosen[i]) continue;
        order[k] = i;
        chosen[i] = true;
        dfs(k + 1);
        chosen[i] = false;
    }
}

// 用vector来存方案，用二进制数来记录状态
vector<int> path;
void dfs(int u, int state)
{
    if (u == n)
    {
        vector<int>::iterator i;
        for (i = path.begin(); i < path.end(); i++)
            cout << *i << ' ';
        puts("");
    }
    for (int i = 0; i < n; i++)
        if (!(state >> i & 1))
        {
            path.push_back(i + 1);   //用vector来记录方案
            dfs(u + 1, state | 1 << i);
            path.pop_back();
        }
}

NOIP 2012 普及组初赛试题，排列数

排列数 输入两个正整数n，m（1<n<20,1<m<n），在1~n中任取m个数，按字典序从小到大输出所有这样的排列。

//用贪心的方法，贪出来字典序
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int data[N];
bool used[N];
int n, m;
int main()
{
    cin >> n >> m;
    //第一种方案存了起来
    for (int i = 1; i <= m; i++){
        data[i] = i;
        used[i] = true;
    }
    bool flag = true;
    while (flag){
        //输出方案
        for (int i = 1; i <= m; i++) cout << data[i] << ' ';
        puts("");
        flag = false;
        for (int i = m; i >= 1; i--){
            used[data[i]] = false;
            for (int j = data[i] + 1; j <= n; j++){
                if (used[j] == false){
                    data[i] = j;
                    used[j] = true;
                    flag = true;
                    break;
                }
            }
            if (flag){
                for (int k = i + 1; k <= m; k++)
                    for (int j = 1; j <= n; j++)
                        if (used[j] == false){
                            used[j] = true;
                            data[k] = j;
                            break;
                        }
                break;
            }
        }
    }
    return 0;
}