顺序全排列 简单回溯算法详解 [c++]

顺序全排列 简单回溯

目录

• 顺序全排列 简单回溯
• • 例题
  • 题解思路
  • 解释①
  • 尾言

例题

告诉你一个按顺序排列的数字，例如(1,3),(2,6)等，请列出他们的全排列结果。

输入： start = 1 end = 3

输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

题解思路

如果数字比较少，可以用嵌套for循环解题，但是for循环消耗的空间和时间都比较多，不建议使用，所以就需要用到解决全排列问题最常用的class="superseo">算法思路：回溯算法；

需要用到：

used[maxx]用于判断某个数字是否已经被用过；

p[maxx] 用于存放排列的结果；

回溯算法的步骤是 使用数据 -> 输出结果 -> 重置空间 ->继续使用，所以used[paxx]就可以发挥重置的作用，使用后讲其变为flase就相当于重置/退回；

回溯中需要用到递归，index + 1 ，例题中，就相当于先取1为首之后，inedx = 1+1 =2 ，used[2] = true，第二个绑定为2，使用结束后，used[2]重置为flase，inedx = 2+1 =3，used[3] = true，第三个绑定为3，used[3] 重置为false，第一个排列结果就是[1， 2， 3]；

根据这个思路就可以写出代码：

#include 
using namespace std;
const int maxx = 13;
int p[maxx];   // 存放排列结果
bool used[maxx] = { false };  // 判断数字是否用过，且用于回溯(重置)
int sstart,send; // 开始数字和结束数字  解释①

void backk(int index){   // index 为开始数字
    if(index == send + 1){     //设置出口， 如果已经排列到了end+1，说明已经不用排列了，输出排列的组合
        for(int i = sstart;i <= send;i++){
            cout << p[i] << " ";
        }
        cout << endl;
        return ; // 退出
    }
    
    for(int i = sstart;i <= send;i++){
        if(!used[i]){  // 如果used[i] = flase，该数字没有用过的话，就开始递归
            p[index] = i;   // 把数字i放进排列数组中
            used[i] = true;  // 标记已经使用
            backk(index + 1); // 进入递归，送start循环到end
            used[i] = false; // 重置该数字
        }
    }
}

int main(){
    cout << "start: ";
    cin >> sstart;
    cout << "end: ";
    cin >> send;
    backk(sstart);
    return 0;
}

了解完顺序全排列之后，可以接着看看乱序全排列
点击查看 乱序全排列，C++实现

解释①

用sstart和send的原因是在vs中，start和end会和其定义的全局变量发生冲突，产生变量不明确的报错。

---

尾言

感谢您的阅读！
如果文章有错误请留言指出，谢谢！