MSTBL的博客
0%

排列组合问题

发表于 分类于

排列组合问题

输出排列组合这类问题通常是递归的，比较适合用递归求解。可以作为深度优先搜索（DFS）的理解练习。

P1706 全排列问题

本题要求输出 1n n个数的全排列。可以以1n为根节点分别建立一棵树，这棵树每个节点都有n个子节点，深度为n，对这些树组成的森林进行深度优先搜索,每次搜索到叶子节点时输出搜索路径并回溯。遇到用过的数时跳过搜索下一个。这样就可以实现题目要求的功能。

关于建树，我们也可以以“0”作为根节点，将上述n棵树作为它的子树。这样就可以进行单源深搜。

对于如何建树，我们只要在递归里用一层循环：

1
2
3
4
5
6
7
void dfs(int k)
{
    for (int i = 1; i <= n; i++)
    {
            dfs(k + 1);
    }
}

在dfs函数中用一个判断语句同时实现判断是否到达子节点和输出：

1
2
3
4
5
if(k == n)
   {
       print();
       return;
   }

用一个res[]数组来存答案,每次搜索前把i填入res[k + 1]中，因为我们从0开始搜索。为了知道每个数字是否用过，还需要一个used[] 数组来存储1~n是否用过；在下一层搜索前将其改为true，下一层搜索完之后回归。

下面是完整的dfs()函数的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs(int k)
{
    if(k == n)                  //到达叶子结点
    {
        print();
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if(!used[i])
        {
            used[i] = true;     //记录使用情况
            res[k + 1] = i;
            dfs(k + 1);         //递推
            used[i] = false;    //回归
        }
    }
}

此外，由于题目要求每个数字5位场宽，我们还需要设置场宽。这需要用到<iomanip>中的setw()。以下是print函数的实现：

1
2
3
4
5
6
7
8
void print ()
{
    for(int i = 1; i <= n; i++)
    {
        cout << setw(5) << res[i];
    }
    cout << endl;
}

最后还要注意一点的是在主函数中调用的是dfs(0)，用的是上述第二种建树方法，以下几题用的也是此种方法

P1157 组合的输出

本题要求不用递归输出n个数中r个数的全排列。然而我用了递归。如果用递归的话有了上一题的经验就比较简单，稍微修改一下即可。可以在遍历下一层时只遍历比k大的数，这样就能实现功能，还不用判重。下面给出dfs_2()函数的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs_2(int k)
{
    if (b == r)         //n改成r，上题中是n是因为全排列，n=r，下同 还要记得将print()中的n改成r
    {
        res[r] = k;     //这里需要注意一定要把最后一位填上
        print();
        return;
    }
    for (int i = k + 1; i <= n; i++)
    {
        res[b] = k;
        b++;            //b用来记录位数
        search(i);
        b--;
    }
}

P1691 有重复元素的排列问题

本题要求输出重复元素的全排列。也只需在P1706的基础上修改即可。可以记录每个元素的数目，像之前一样进行深搜，不一样的是，遇到用过的元素时将数目-1，直到数目变成0为止再进行类似上面的“剪枝”操作。

不过首先本题的输入就是个问题。需要知道题目中的每个“元素”实际上就是26个字母之一。这样就可以用<string>，先将输入存入一个字符串，再对其进行处理：

1
2
3
4
5
6
7
8
9
10
void input()
{
    cin >> n;
    cin >> tmp;
    for (int i = 0; i < n; i++)
    {
        num[tmp[i] - 96]++;     //记录用过的次数 先-96会好理解一些
    }
}

经过了上面两个题，本题的深搜代码本身不难改，下面是dfs_3()的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs_3(int k)
{
    if (k == n)
    {
        print();
        return;
    }
    for (int i = 1; i <= 26; i++)   //每次对26个字母进行遍历
    {
        if (num[i])                 //如果这个元素还有
        {
            num[i]--;
            res[k] = i;
            dfs_3(k + 1);
            num[i]++;
        }
    }
}

然而，本题的输出并不是很直接，我用了显式类型转换：

1
2
3
4
5
6
7
8
9
10
void print()
{
    for (int i = 0; i < n; i++)
    {
        char tmpchar = static_cast<char>(res[i] + 96); //显式类型转换 记得把96加回去
        cout << tmpchar;
    }
    cout << endl;
    sum++;                          //排列总数，在其他地方迭代也可
}