当前位置：首页 > news >正文

排列问题方法总结（递归+迭代）

news 2025/7/1 3:53:49

递归

一、逐步生成结果法（无序）

#include<iostream>  
#include<vector>  
#include<string>
#include<algorithm>using namespace std;vector<string> GetChild(int n,int curIndex){vector<string> now;vector<string> cur;if (curIndex == 1) {  now.push_back("1");cur=now;return cur;}cur=GetChild(n, curIndex - 1);for (string temp : cur) {now.push_back(temp + to_string(curIndex));now.push_back(to_string(curIndex) + temp);for (int j = 1; j < temp.size(); j++) {now.push_back(temp.substr(0, j) + to_string(curIndex) + temp.substr(j));}}cur = now;return cur;
}int main(void) {int n,k;cin >> n>>k;// 获取子集vector<string>ans = GetChild(n,n); // 存放子集的数组//排序sort(ans.begin(), ans.end());// 输出子集个数int n_ = ans.size();cout << "子集个数：" << n_ << endl;// 输出子集  for (auto sub_set : ans) {cout << sub_set << endl;}cout<<endl;// 输出第k个子集cout << ans[k - 1];return 0;
}

这个代码主要就是讲的是逐步生成结果，然后它主要就是利用了一个递归的思想。

首先就是先假设我求出来了前 n -1 个数的排列，然后我作为老板我只需要去排列第 n 个数。它的排法一共有三种，首先就是可以把这个数插在这个排列的前面，也可以插在排列的后面。除此之外也可以插在这个排列的中间的任何一个空里面。

总的来说他主要就是将这个新的数插到一切可以插的空里面，然后记录即可。

对于递归出口，我们要设一个变量，用来代表我当前是对于第几个元素进行操作，当达到第一个元素时，那么就新建一个数组，然后将这个第一个元素放进去，代表我是一个数的排列，就是它本身。

但是这种方法求出来的排列并不是有序的，我们在最后输出结果的时候要记得对这个排列进行排序。（后面有已序的求法）

递归的思想前面也说过，它主要就是一种老板思维，就是我不需要去考虑一些细节上的东西，相当于把一些重复性的工作让员工去做，然后我只需要进行最后一步，或者说是特定的一步即可。然后注意初始条件。

二、基于交换的递归方法（交换完排序则是有序）

#include<iostream>  
#include<vector>  
#include<string>  
#include<algorithm>  using namespace std;vector<string> ans;void GetChild(string s, int n, int curIndex) {cout << string(curIndex, ' ') << "+-- " << s << endl; // 打印当前状态  if (curIndex == n) {ans.push_back(s);cout << string(curIndex, ' ') << "|   Found permutation: " << s << endl; // 指示找到的排列  return; // 退出递归  }for (int i = curIndex; i < n; i++) {swap(s[i], s[curIndex]);sort(s.begin() + curIndex + 1, s.end()); // 交换后，将curIndex之后的元素排序(保证字典序)GetChild(s, n, curIndex + 1);swap(s[i], s[curIndex]); // 还原交换  }cout << string(curIndex, ' ') << "+-- Exiting depth " << curIndex << ": " << s << endl; // 打印退出当前状态  }
int main(void) {int n;cin >> n;// 初始化字符串并排序  string s = "";for (int i = 1; i <= n; i++) {s += to_string(i);}GetChild(s, n, 0); // 生成所有排列  // 输出排列个数  int n_ = ans.size();cout << "排列个数：" << n_ << endl;// 输出所有排列  for (const auto& sub_set : ans) {cout << sub_set << endl;}return 0;
}

CurIndex 指的是当前元素的下标。递归操作时先交换i处和当前下标元素的位置，然后对后面的元素进行一个升序排序，就是字典序。

然后递归的调用这个函数，最后再还原交换。

当我的CurIndex 等于 n 的时候，相当于我从第一个元素遍历到第二个元素，然后存入s 。（s在交换的过程中被改变，初始化为升序排列）

三、逐个交换大法（有序）

#include<iostream>  
#include<vector>  
#include<string>  
#include<algorithm>  using namespace std;vector<string> ans;
int cnt = 0;
int flag = 0;int Mcount(string s, char c) {int count = 0;for (int i = 0; i < s.size(); i++) {if (s[i] == c) {count++;}}return count;
}void GetChild(string s, string arr,int k) {if (flag == 1) {return;}if (s.size() == arr.size()) {cnt++;ans.push_back(s);if (cnt == k) {flag = 1;    }}for (int i = 0; i < arr.size(); i++) {char c = arr[i];if (Mcount(s,c) < Mcount(arr,c)) {GetChild(s + c, arr, k);}if (flag == 1) {return;}}
}
int main(void) {int n,k;cin >> n>>k;// 初始化字符串并排序  string s = "";for (int i = 1; i <= n; i++) {s += to_string(i);}GetChild("", s, k); // 生成所有排列  // 输出排列个数  int n_ = ans.size();cout << "排列个数：" << n_ << endl;// 输出所有排列  for (const auto& sub_set : ans) {cout << sub_set << endl;}cout << endl;cout<<ans[k-1]<<endl;return 0;
}

Mcount参数是用来记录当前元素在字符串中的个数。

Getchild 函数里面进行递归操作。

递归出口就是 s 的大小等于数组大小，然后记录这个数字里面字符串的数目，当它等于 k 的时候，我们就让递归函数退出。

然后基本的递归操作就是记录当前的字符，然后判断在当前排列和数组中该字符的个数。如果说当前字符串中，该字符个数小于数组中的话，就把当前字符加到我的当前s的后面，然后递归的去求。

这个是一个有序的递归方法。主要是因为对于元素的添加是有序的。

递归退出主要是利用一个 flag 标志，当满足条件的时候改变这个标志，然后在递归函数的出口前判断这个标志。

迭代：

逐步生成迭代大法：

#include<iostream>  
#include<vector>  
#include<string>
#include<algorithm>using namespace std;vector<string> GetChild(int n) {vector<string> cur;cur.push_back("1");for (int i = 2; i <= n; i++) {vector<string> now;for (string temp : cur) {now.push_back(temp + to_string(i));now.push_back(to_string(i) + temp);for (int j = 1; j < temp.size(); j++) {now.push_back(temp.substr(0, j) + to_string(i) + temp.substr(j));}}cur = now;}return cur;
}int main(void) {int n,k;cin >> n>>k;// 获取子集vector<string>ans = GetChild(n); // 存放子集的数组//排序sort(ans.begin(), ans.end());// 输出子集个数int n_ = ans.size();cout << "子集个数：" << n_ << endl;// 输出子集  for (auto sub_set : ans) {cout << sub_set << endl;}cout<<endl;// 输出第k个子集cout << ans[k - 1];return 0;
}

这个逐步生成的迭代大法其实和上面那个递归的逐步生成方法类似，它的思想也是一致的。首先我是建立一个字符串数组，然后先放入第一个元素，也就是1。

然后紧接着我遍历所有元素，对于当前的元素的话，它有三种可能的放置方式，首先是放在原有排列的前面，还有一种是放在排列后面，或者是插在这个排列的中间。总而言之它就是放在所有能放的位置.

利用排列性质的迭代算法：

#include<iostream>  
#include<vector>  
#include<algorithm>using namespace std;vector<vector<int>> GetChild(int n) {int row = n;vector<vector<int>> cur;for (int i = 0; i < row; i++) {vector<int> temp(n, 0);temp[i] = 1;cur.push_back(temp);}for (int i = 2; i <= n; i++) {vector<vector<int>> now;vector<int> temp;for (int j = 0; j < cur.size(); j++) {for (int k = 0; k < n; k++) {temp = cur[j];if (temp[k] == 0) {temp[k] = i;now.push_back(temp);}}}cur = now;}return cur;
}int main(void) {int n,k;cin >> n>>k;// 获取子集vector<vector<int>>ans = GetChild(n); // 存放子集的数组//排序sort(ans.begin(), ans.end());// 输出子集个数int n_ = ans.size();cout << "子集个数：" << n_ << endl;// 输出子集  for (auto sub_set : ans) {cout << "{ ";for (auto elem : sub_set) {cout << elem << " ";}cout << "}" << endl;}// 输出第k个子集for (auto elem : ans[k - 1]) {cout << elem;}return 0;
}