有关回溯的相关排列组合遍历

偏执的太偏执、 2022-05-18 08:23 167阅读 0赞

**目录**

无相同元素

全排列

排列A（n,m）

组合C（n,m）

有相同元素

全排列

排列A（n,m）

组合C（n,m）

**最近刚刚学习了递归，回溯算法来进行深度搜索。对一些题目有一些感触，顺便写下变体的解法。**

**此类深搜主要分为无相同元素和有相同元素，下面又分好几种情况。**

# 无相同元素 #

## 全排列 ##

void dfs(int i){
        if(n==i){
            for(int j=0;j<n;j++)
                printf("%5d",a[j]);
            printf("\n");
     
        }
        else
            for(int j=1;j<=n;j++)
                if(b[j]==0){
                    b[j]=1;
                    a[i]=j;
                    dfs(i+1);
                    b[j]=0;
                }
     
     
        
     
    }

**例题1：**

> ## 问题 A: 全排列问题 ##
> 
> 时间限制: 1 Sec 内存限制: 128 MB  
> 提交: 123 解决: 71  
> \[[提交][Link 1]\]\[[状态][Link 2]\]\[[讨论版][Link 3]\]\[命题人: 外部导入\]
> 
> ## 题目描述 ##
> 
> 输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
> 
> ## 输入 ##
> 
> 输入 n(1≤n≤9)
> 
> ## 输出 ##
> 
> 由1～n组成的所有不重复的数字序列，每行一个序列。每个数字占5列。
> 
> ## 样例输入 ##
> 
>     4
> 
> ## 样例输出 ##
> 
>     1    2    3    4
>         1    2    4    3
>         1    3    2    4
>         1    3    4    2
>         1    4    2    3
>         1    4    3    2
>         2    1    3    4
>         2    1    4    3
>         2    3    1    4
>         2    3    4    1
>         2    4    1    3
>         2    1    4    3 
>         3    1    2    4
>         3    1    4    2
>         3    2    1    4
>         3    2    4    1
>         3    4    1    2
>         3    4    2    1
>         4    1    2    3
>         4    1    3    2
>         4    2    1    3
>         4    2    3    1
>         4    3    1    2
>         4    3    2    1
> 
> \[[提交][Link 1]\]\[[状态][Link 2]\]

## 排列A（n,m） ##

void dfs(int i,int l){
        if(l==n){
            for(int j=0;j<n;j++)
                cout<<b[j];
            cout<<"\n";
        }else
            for(int j=0;j<m;j++)
                if(a[j]==0){
                    a[j]=1;
                    b[i]=j+1;
                    dfs(i+1,l+1);
                    a[j]=0;
                }
    }

**例题2：**

> ## 问题 B: 输出N个不同字母的全排列 ##
> 
> 时间限制: 1 Sec 内存限制: 128 MB  
> 提交: 223 解决: 83  
> \[[提交][Link 4]\]\[[状态][Link 5]\]\[[讨论版][Link 6]\]\[命题人: 外部导入\]
> 
> ## 题目描述 ##
> 
> 输入正整数n（n＜10），输出ABCD...n个不同字母的全排列，输出时按升序每行显示一个结果
> 
> ## 输入 ##
> 
> 正整数N（N＜10）
> 
> ## 输出 ##
> 
> N个字母的全排列，升序排列，每行一个
> 
> ## 样例输入 ##
> 
>     【测试样例1】
>     1
>     【测试样例2】
>     2
>     【测试样例3】
>     3
>     【测试样例4】
>     4
> 
> ## 样例输出 ##
> 
>     【测试样例1】
>     A
>     【测试样例2】
>     AB
>     BA
>     【测试样例3】
>     ABC
>     ACB
>     BAC
>     BCA
>     CAB
>     CBA
>     【测试样例4】
>     ABCD
>     ABDC
>     ACBD
>     ACDB
>     ADBC
>     ADCB
>     BACD
>     BADC
>     BCAD
>     BCDA
>     BDAC
>     BDCA
>     CABD
>     CADB
>     CBAD
>     CBDA
>     CDAC
>     CDCA
>     DABC
>     DACB
>     DBAC
>     DBCA
>     DCAB
>     DCBA
> 
> \[[提交][Link 4]\]\[[状态][Link 5]\]

## 组合C（n,m） ##

void dfs(int i,int l,int k){
        if(l==n){
            for(int j=0;j<n;j++)
                cout<<b[j];
            cout<<"\n";
        }else
            for(int j=k;j<m;j++){
                if(a[j]==0){
                    a[j]=1;
                    b[i]=j+1;
                    dfs(i+1,l+1,k);
                    a[j]=0;
                }
                k++;
            }
    
    }

**例题3：**

> ## 问题 D: 组合的输出 ##
> 
> 时间限制: 1 Sec 内存限制: 128 MB  
> 提交: 111 解决: 64  
> \[[提交][Link 7]\]\[[状态][Link 8]\]\[[讨论版][Link 9]\]\[命题人: 外部导入\]
> 
> ## 题目描述 ##
> 
> 排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r<＝n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。
> 
> 现要求你用递归的方法输出所有组合。
> 
> 例如n＝5，r＝3，所有组合为：
> 
> l 2 3 l 2 4 1 2 5 l 3 4 l 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
> 
> ## 输入 ##
> 
> 一行两个自然数n、r(1<n<21，1<＝r<＝n)。
> 
> ## 输出 ##
> 
> 所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。
> 
> ## 样例输入 ##
> 
>     5 3
> 
> ## 样例输出 ##
> 
>     1  2  3
>       1  2  4
>       1  2  5
>       1  3  4
>       1  3  5
>       1  4  5
>       2  3  4
>       2  3  5
>       2  4  5
>       3  4  5
> 
> \[[提交][Link 7]\]\[[状态][Link 8]\]

#  #

# 有相同元素 #

## 全排列 ##

#include <iostream>
    #include<map>
    using namespace std;
    int n,m;
    int a[15]={0};
    char b[15];
    char c[15];
    map<char,int> counts;
    void dfs(int i){
       if(i==n){
           for(int j=0;j<n;j++)
               cout<<b[j];
           cout<<"\n";
       }else{
           for(map<char,int>::iterator it=counts.begin();it!=counts.end();it++)
               if(it->second!=0){
                   b[i]=it->first;
                   it->second--;
                   dfs(i+1);
                   it->second++;
               }
    
       }
    
    }
    
    int main(){
        char c;
        cout<<"有相同元素全排列"<<endl;
        cin>>n;
        cout<<"输入元素"<<endl;
        for(int i=0;i<n;i++){
            cin>>c;
            if(counts.count(c)==0)
                counts[c]=1;
            else
                counts[c]++;
        }
        dfs(0);
    }

**例题4：**

> ## 问题 E: 有重复元素的排列问题 ##
> 
> 时间限制: 1 Sec 内存限制: 128 MB  
> 提交: 147 解决: 62  
> \[[提交][Link 10]\]\[[状态][Link 11]\]\[[讨论版][Link 12]\]\[命题人: 外部导入\]
> 
> ## 题目描述 ##
> 
> 设R=\{ r1, r2 , …, rn\}是要进行排列的n个元素。其中元素r1, r2 , …, rn可能相同。试设计一个算法，列出R的所有不同排列。
> 
> 给定n 以及待排列的n 个元素。计算出这n 个元素的所有不同排列。
> 
> ## 输入 ##
> 
> 输入数据的第1 行是元素个数n，1≤n≤500。接下来的1 行是待排列的n个元素。
> 
> ## 输出 ##
> 
> 计算出的n个元素的所有不同排列并输出。文件最后1行中的数是排列总数。
> 
> ## 样例输入 ##
> 
>     4
>     aacc
> 
> ## 样例输出 ##
> 
>     aacc
>     acac
>     acca
>     caac
>     caca
>     ccaa
>     6
> 
> \[[提交][Link 10]\]\[[状态][Link 11]\]

**例题5：**

> ## 问题 C: 排列棋子 ##
> 
> 时间限制: 1 Sec 内存限制: 128 MB  
> 提交: 135 解决: 96  
> \[[提交][Link 13]\]\[[状态][Link 14]\]\[[讨论版][Link 15]\]\[命题人: 外部导入\]
> 
> ## 题目描述 ##
> 
> 将M个白棋子与N个黑棋子排成一行，可以排成多种不同的图案。例如：2个白棋子和2个黑棋子，一共可以排成如下图所示的6种图案（根据组合数计算公式：![pimg1078_1.bmp][]）
> 
> ![说明: http://10.60.64.213:8080/JudgeOnline/images/4736\_2.bmp][http_10.60.64.213_8080_JudgeOnline_images_4736_2.bmp]
> 
> 请你编写一段程序，输出M个白棋子与N个黑棋子能够组成的所有图案。
> 
> 为了避免程序输出结果过多导致严重超时，特别限制：1≤M,N≤6
> 
> ## 输入 ##
> 
> 两个正整数M,N表示白棋子与黑棋子的数量，并且满足1≤M,N≤6 
> 
> ## 输出 ##
> 
> M个白棋子与N个黑棋子可以排列的所有图案。  
> 要求：每行输出一种图案，白棋子用0表示，黑棋子用1表示，按升序输出
> 
> ## 样例输入 ##
> 
>     <span style="color:#333333">【测试样例1】
>     2 1
>     【测试样例2】
>     2 2
>     【测试样例3】
>     2 3</span>
> 
> ## 样例输出 ##
> 
>     <span style="color:#333333">【测试样例1】
>     001
>     010
>     100
>     【测试样例2】
>     0011
>     0101
>     0110
>     1001
>     1010
>     1100
>     【测试样例3】
>     00111
>     01011
>     01101
>     01110
>     10011
>     10101
>     10110
>     11001
>     11010
>     11100</span>
> 
> ## 提示 ##
> 
> shj
> 
> \[[提交][Link 13]\]\[[状态][Link 14]\]

以上例题均来自WLACM

[Link 1]: http://wlacm.com/submitpage.php?cid=1236&pid=0&langmask=262141
[Link 2]: http://wlacm.com/problemstatus.php?id=1089
[Link 3]: http://wlacm.com/bbs.php?pid=1089&cid=1236
[Link 4]: http://wlacm.com/submitpage.php?cid=1236&pid=1&langmask=262141
[Link 5]: http://wlacm.com/problemstatus.php?id=1077
[Link 6]: http://wlacm.com/bbs.php?pid=1077&cid=1236
[Link 7]: http://wlacm.com/submitpage.php?cid=1236&pid=3&langmask=262141
[Link 8]: http://wlacm.com/problemstatus.php?id=1090
[Link 9]: http://wlacm.com/bbs.php?pid=1090&cid=1236
[Link 10]: http://wlacm.com/submitpage.php?cid=1236&pid=4&langmask=262141
[Link 11]: http://wlacm.com/problemstatus.php?id=1091
[Link 12]: http://wlacm.com/bbs.php?pid=1091&cid=1236
[Link 13]: http://wlacm.com/submitpage.php?cid=1236&pid=2&langmask=262141
[Link 14]: http://wlacm.com/problemstatus.php?id=1078
[Link 15]: http://wlacm.com/bbs.php?pid=1078&cid=1236
[pimg1078_1.bmp]: /images/20220518/3d4c8f75c69c4a95a23a5b0823ff0b63.png
[http_10.60.64.213_8080_JudgeOnline_images_4736_2.bmp]: /images/20220518/d0d7deede2654679b6548161875039c7.png