首页 > 代码库 > 全排列问题
全排列问题
全排列问题
基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题
给出一个字符串S（可能又重复的字符），按照字典序从小到大，输出S包括的字符组成的所有排列。例如：S = "1312"，
输出为：
1123
1132
1213
1231
1312
1321
2113
2131
2311
3112
3121
3211
Input
输入一个字符串S（S的长度 <= 9，且只包括0 - 9的阿拉伯数字）
Output
输出S所包含的字符组成的所有排列
Input示例
1312
Output示例
112311321213123113121321211321312311311231213211
①用STL//教程在紫书187页
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;char QAQ[15];int n;int main(){ scanf("%s",QAQ); n=strlen(QAQ); sort(QAQ,QAQ+n); do { puts(QAQ); } while (next_permutation(QAQ,QAQ+n)); return 0;}
②用递归代替重，递归里放一个循环
#include <iostream>#include <string>#include <algorithm>#include <vector>#include <map>using namespace std;typedef string::const_iterator sit;bool vis[9];map<string,bool> m;void dfs(const string& s,sit pos,string& st) { if (st.size()==s.length()&&m.find(st)==m.end()) { m[st]=true; cout<<st<<endl; return; } for (sit i=s.begin(); i!=s.end(); ++i) if (vis[i-s.begin()]==false) { vis[i-s.begin()]=true; st.push_back(*i); dfs(s,i+1,st); st.erase(st.end()-1,st.end()); vis[i-s.begin()]=false; }}int main() { string s; cin>>s; sort(s.begin(),s.end()); string temp; dfs(s,s.begin(),temp); return 0;}
全排列问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。