输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
//全排列算法+最后map排序即可 #include<iostream> (720)#include<cstring> #include<map> using namespace std; map<string,int> mm; void Array(char *s,int k,int m) { if(k==m) mm[s]++; else { for(int j=k;j<=m;j++) { swap(s[j],s[k]); Array(s,k+1,m); swap(s[j],s[k]); } } } int main() { char s[10]; cin>>s; Array(s,0,strlen(s)-1); auto ot=mm.end(); ot--; for(auto it=mm.begin();it!=mm.end();it++) { if(it==mm.begin()) cout<<'['<<it->first<<','<<" "; else if(it==ot) cout<<it->first<<']'; else cout<<it->first<<','<<" "; } }
const readline = require('readline') const rl = readline.createInterface({ input: process.stdin, ouput: process.stdout }) let inArr = [] rl.on('line',line=>{ if(!line) return inArr.push(line.trim()) if(inArr.length === 1){ let arr = inArr[0].split('') let res = permuteUnique(arr).map(e=>e.join('')) res.sort() let str = '' for (let i = 0; i < res.length; i++) { if(i==0){ str += '['+res[i] +', ' }else if(i==res.length-1){ str += res[i] +']' }else{ str += res[i]+', ' } } console.log(str) } }) var permuteUnique = function(nums) { if (nums.length === 0) { return []; } if (nums.length === 1) { return [nums]; } let [num, ...restNums] = nums; let resArr=permuteUnique(restNums).reduce((res, iter) => { let iterRes = []; for (let i = 0; i <= iter.length; i++) { let tmp = [...iter]; tmp.splice(i, 0, num); iterRes.push(tmp); } return res.concat(iterRes); }, []); let res={} resArr.forEach(item=>{ res[item]=item; }); return Object.values(res) };
//dfs+set去重 #include <bits/stdc++.h> using namespace std; void dfs(int len,string temp,string &str,vector<bool> &vis,set<string> &ans){ if(len>=str.size()){ ans.insert(temp); return; } for(int i=0;i<str.size();i++){ if(vis[i]) continue; vis[i]=true; dfs(len+1,temp+str[i],str,vis,ans); vis[i]=false; } } int main(){ string str; set<string> ans; vector<bool> vis(str.size(),false); cin>>str; dfs(0,"",str,vis,ans); set<string>::iterator it=ans.begin(); cout<<"["; while(it!=ans.end()){ cout<<*it; if(++it!=ans.end()) cout<<", "; } cout<<"]"; return 0; }
#include <bits/stdc++.h> using namespace std; int main() { string str; bool isVirgin = true; //判断是不是第一次 while(getline(cin,str)) { string result = ""; //结果字符串 sort(str.begin(), str.end()); //题目中给出的字符串不一定是升序,有个测试点是aA,所以我们自己先升序排列一遍 do{ if(isVirgin) { result += "[" + str; isVirgin = false; } else { result += ", " + str; //注意逗号后面有个空格 } }while(next_permutation(str.begin(),str.end())); //全排列 result += "]"; cout << result << endl; } return 0; }
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { //标准的全排列问题,有重复的全排列,偷懒的就用set去重,答案要求字典顺序输出,就用TreeSet咯, static TreeSet<String> output = new TreeSet<>(); public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); String s = bf.readLine(); backtrack(s.toCharArray(), 0, s.length()); StringBuilder sb = new StringBuilder(); sb.append('['); for (String item : output) { sb.append(item).append(",").append(" "); } System.out.println(sb.substring(0, sb.length() - 2) + "]"); } //回溯算法 private static void backtrack(char[] chars, int first, int n) { if (first == n) { output.add(String.valueOf(chars)); return; } for (int i = first; i < n; i++) { swap(chars, first, i); backtrack(chars, first + 1, n); //回溯 swap(chars, first, i); } } private static void swap(char[] chars, int i, int j) { char temp = chars[i]; chars[i] = chars[j]; chars[j] = temp; } }
#include <bits/stdc++.h> using namespace std; int main(){ string s; bool first; while(cin>>s){ first = true; string t = ""; sort(s.begin(), s.end()); do{ if(first){ t = "[" + s; first = false; }else{ t += ", " + s; } }while(next_permutation(s.begin(), s.end())); t += "]"; cout<<t<<endl; } return 0; }
input_str = input() def back_track(tmp,l, r, res): if l == r: res.append(''.join(tmp)) return else: cache = set() for i in range(l, r + 1): if tmp[i] in cache: pass else: cache.add(tmp[i]) tmp[l], tmp[i] = tmp[i], tmp[l] back_track(tmp, l + 1, r, res) tmp[l], tmp[i] = tmp[i], tmp[l] result = [] back_track(list(input_str), 0, len(input_str)-1, result) # 按字典序打印出 result.sort() print("[" + ', '.join(result) + "]")
using System; using System.Collections.Generic; using System.IO; using System.Text; class Test { static List<string> output = new List<string>(); static void Main(string[] args) { string input = Console.ReadLine(); backtrack(input.ToCharArray(),0 , input.Length); StringBuilder s = new StringBuilder("["); delSame(); for(int i = 0;i < output.Count; i++){ s.Append(output[i]).Append(",").Append(" "); } s.Remove(s.Length - 2, 2); s.Append("]"); Console.WriteLine(s); } private static void backtrack(char[] chars , int first , int n){ if(first == n){ output.Add(new string(chars)); return; } for(int i = first; i < n; i++){ swap(chars, first , i); backtrack(chars, first + 1, n); swap(chars, first , i); } } private static void swap(char[] chars , int i , int j){ char temp = chars[j]; chars[j] = chars[i]; chars[i] = temp; } private static void delSame(){//去重复 for (int i = 0; i < output.Count; i++) //外循环是循环的次数 { for (int j = output.Count - 1 ; j > i; j--) //内循环是 外循环一次比较的次数 { if (output[i] == output[j]) { output.RemoveAt(j); } } } } }
#include<iostream> #include<string> #include<vector> #include<algorithm> using namespace std; vector<string> res; void dfs(string str,int begin) { if(begin==str.size()-1) { res.push_back(str); return ; } for(int i=begin;i<str.size();i++) { if(i!=begin&&str[i]==str[begin]) continue; swap(str[i],str[begin]); dfs(str,begin+1); swap(str[i],str[begin]); } } int main() { string str; cin>>str; dfs(str,0); sort(res.begin(),res.end()); string s; s+="["+res[0]; for(int i=1;i<res.size();i++) { s+=", "+res[i]; } s+="]"; cout<<s<<endl; return 0; }
#include<bits/stdc++.h> using namespace std; vector<string>res; string t; void bk(string s,vector<int>&vis) { if(t.size()==s.size())res.push_back(t); for(int i=0;i<s.size();i++) { if(vis[i]==1)continue; if(i>0&&s[i]==s[i-1]&&vis[i-1]==0)continue; t.push_back(s[i]); vis[i]=1; bk(s,vis); t.pop_back(); vis[i]=0; } } int main() { string s; cin>>s; sort(s.begin(),s.end()); vector<int>vis(s.size(),0); bk(s,vis); cout<<'['; for(int i=0;i<res.size()-1;i++) { cout<<res[i]<<','<<" "; } cout<<res.back()<<']'; return 0; }
//深度优先搜索 #include <iostream> #include <string> #include <vector> #include <algorithm> #include <limits.h> #include <set> using namespace std; void DFS_SSP(string s, int k, int m, set<string> &strset) { if (k == m) { strset.insert(s); } else { for (int i = k; i < m;i++) { swap(s[i], s[k]); DFS_SSP(s, k+1, m, strset); swap(s[i], s[k]); } } } void StringSullPermutation() { string s; cin>>s; int len = s.size(); set<string> strset; //set自动排序和去重 DFS_SSP(s, 0, len, strset); //输出 set<string>::iterator it = strset.begin(); cout << "["; while (it != strset.end()) { cout << *it; if (++it != strset.end()) { cout << ", "; } } cout << "]" <<endl; } int main(){ StringSullPermutation(); return 0; }
回溯法 主要在于重复字符的处理 #include<iostream> (720)#include<string> #include<vector> (721)#include<algorithm> using namespace std; void BackTrack(string &s, string &temp, vector<string> &ans, vector<bool> &vis){ if (temp.size() == s.size()){ ans.push_back(temp); return ; } for (int i = 0; i < s.size(); i++){ if (vis[i] || (i > 0 && !vis[i-1] && s[i] == s[i-1])) //控制访问重复或已经访问的字符 continue; vis[i] = true; temp.push_back(s[i]); BackTrack(s, temp, ans, vis); vis[i] = false; temp.pop_back(); } return ; } int main(void){ string s; cin>>s; sort(s.begin(), s.end()); vector<string> ans; string temp; vector<bool> vis(s.size(), false); BackTrack(s, temp, ans, vis); cout<<"["; for (int i = 0; i < ans.size(); i++){ if (i == ans.size()-1) cout<<ans[i]; else cout<<ans[i]<<", "; } cout<<"]"<<endl; }
import java.util.ArrayList; import java.util.List; import java.util.Scanner; import java.util.Stack; import java.util.TreeSet; public class Permutation { //华为机试,字符串处理,排列组合 public static void main(String[] args) { Scanner input = new Scanner(System.in); String str = input.nextLine(); List<Character> charList=new ArrayList<Character>(); Stack<Character> result=new Stack<Character>(); TreeSet<String> resultSet = new TreeSet<String>(); //去重加排序 for(int i = 0;i < str.length();i++){ charList.add(str.charAt(i)); } play(charList,result,resultSet); System.out.println(resultSet); input.close(); } public static void play(List<Character> charList,Stack<Character> result,TreeSet<String> resultSet){ //如果size为1,说明已经排列到最后一个了 if(charList.size() == 1) { result.push(charList.get(0)); resultSet.add(result.toString().replaceAll("[^a-zA-Z]", "")); result.pop(); }else{ for(int i=0;i<charList.size();i++){ //逐个压栈排列 result.push(charList.get(i)); List<Character> tmp=new ArrayList<Character>(); for(Character a:charList){ tmp.add(a); } //去掉已经压栈的字符 tmp.remove(i); //排列子序列 play(tmp,result,resultSet); //移除已排列字符 result.pop(); } } } }
//咋又是全排列啊 import java.util.*; public class Main { public ArrayList<String> Permutation(String str) { //全排列问题,之前做过哦,是带重复字符的。 //还记得怎么做的吗 ArrayList<String> result=new ArrayList<>(); if(str.length()<=0) return result; boolean used[] = new boolean[str.length()]; char stack[] = new char[str.length()]; sub(stack,str,0,used,result); Comparator<String> c = (x,y)->{ return x.compareTo(y); }; result.sort(c); return result; } private void sub(char stack[],String str,int seat,boolean used[],ArrayList<String> result){ if(seat==str.length()){ //把stack变为一个字符串,带重复字符哦 result.add(new String(stack)); return; } for(int i=0;i<str.length();++i){ if(!used[i]){ stack[seat]=str.charAt(i); used[i]=true; sub(stack,str,seat+1,used,result); used[i]=false; while(i+1<str.length()&&str.charAt(i+1)==str.charAt(i)) i++;//去重 } } } public static void main(String args[]){ Scanner scanner = new Scanner(System.in); System.out.println(new Main().Permutation(scanner.nextLine())); scanner.close(); //我擦,还有顺序的要求吗?坑人? } }
竟然要输出字符串,出题的人这样搞就没意思了啊。 单次输入 通过 import sys ss = sys.stdin.readline().strip() def perm(ss): if len(ss) <= 1: return [ss] ans = set() for i in range(len(ss)): for j in perm(ss[:i]+ss[i+1:]): ans.add(ss[i]+j) return sorted(list(ans)) print('[' + ", ".join(perm(ss)) + ']') 循环输入 不通过 ???
import sys while True: try: ss = sys.stdin.readline().strip() def perm(ss): if len(ss) <= 1: return [ss] ans = set() for i in range(len(ss)): for j in perm(ss[:i]+ss[i+1:]): ans.add(ss[i]+j) return sorted(list(ans)) print('[' + ", ".join(perm(ss)) + ']') except: pass