浏览 3006 次
锁定老帖子 主题:带重复数字的全排列
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2009-04-16
最后修改:2009-06-09
public class Permutation { private int[] a; public Permutation(int[] a) { this.a = a; } public boolean isOk(int b,int e){//判断是否重复 if(b < e){ for(int i = b; i < e; i++){ if(a[i] == a[e]) return false; } } return true; } public void permutation(int k){ if(k >= a.length){ print(); }else{ for(int i = k; i < a.length; i++){ if(isOk(k,i)){ swap(i,k); permutation( k+1 ); swap(i,k); } } } } private void swap( int i, int k ) { int temp = a[i]; a[i] = a[k]; a[k] = temp; } private void print() { for( int i = 0; i < a.length; i++ ) { System.out.print(a[i] + " "); } System.out.println(); } public static void main( String[] args ) { Permutation p = new Permutation(new int[]{1,2,2,2}); p.permutation( 0 ); } } c++ STL algorithm中有next_permutation可以直接调用,ACM的时候经常偷懒用这个,呵呵。 学以致用:poj 1731 http://acm.pku.edu.cn/JudgeOnline/problem?id=1731 #include<iostream> #include<algorithm> #include<vector> #include<string> using namespace std; string goods; vector<string> v; void swap(string &str,int i, int j){ char temp = str[i]; str[i] = str[j]; str[j] = temp; } bool ok(int i, int j){ if( i < j){ for(int k = i; k < j; k++){ if(goods[k] == goods[j]) return false; } } return true; } void backtrack(int i){ if(i >= goods.length()){ v.push_back(goods); } for(int j = i; j < goods.length(); j++){ if(ok(i,j)){ swap(goods,i,j); backtrack(i + 1); swap(goods,i,j); } } } int main(){ cin >> goods; backtrack(0); sort(v.begin(),v.end()); for(int i = 0; i < v.size(); i++){ cout << v[i] << endl; } } poj1256 http://acm.pku.edu.cn/JudgeOnline/problem?id=1256 这道题需要一种特殊的数序输出: An upper case letter goes before the corresponding lower case letter. So the right order of letters is 'A'<'a'<'B'<'b'<...<'Z'<'z'. 我们只需要定义一个正确的比较函数就可以了 bool cmp(const string &str1,const string &str2){ int i; int m_len = min(str1.length(), str2.length()); for(i = 0; i < m_len; i++){ if(str1[i] != str2[i]) break; } if(i == m_len){ return str1.length() < str2.length(); }else if(tolower(str1[i]) == tolower(str2[i])) { return str1[i] < str2[i]; }else{ return tolower(str1[i]) < tolower(str2[i]); } } 或者 bool cmp(char c1,char c2){ if(tolower(c1) == tolower(c2)) return c1 < c2; else return tolower(c1) < tolower(c2); } 这样我们的代码就出来了: #include<iostream> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<cmath> using namespace std; string str; vector<string> permutations; bool cmp(const string &str1,const string &str2){ int i; int m_len = min(str1.length(), str2.length()); for(i = 0; i < m_len; i++){ if(str1[i] != str2[i]) break; } if(i == m_len){ return str1.length() < str2.length(); }else if(tolower(str1[i]) == tolower(str2[i])) { return str1[i] < str2[i]; }else{ return tolower(str1[i]) < tolower(str2[i]); } } void swap(int i,int j){ char temp = str[i]; str[i] = str[j]; str[j] = temp; } bool isOk(int i,int j){ if(i < j){ int k; for(k = i; k < j; k++){ if(str[k] == str[j]) return false; } } return true; } void backtrack(int i){ if( i >= str.length()){ permutations.push_back(str); return; } int j; for(j = i; j < str.length(); j++){ if(isOk(i,j)){ swap(i,j); backtrack(i+1); swap(i,j); } } } int main(){ int n; cin >> n; int i,j; for(i = 0; i < n; i++){ cin >> str; permutations.clear(); backtrack(0); sort(permutations.begin(),permutations.end(),cmp); for(j = 0; j < permutations.size(); j++){ cout << permutations[j] << endl; } } } 我们还是用STL来爽爽这道题吧: #include<iostream> #include<string> #include<cstring> #include<algorithm> using namespace std; string str; bool cmp(char c1,char c2){ if(tolower(c1) == tolower(c2)) return c1 < c2; else return tolower(c1) < tolower(c2); } int main(){ int n; cin >> n; int i,j; for(i = 0; i < n; i++){ cin >> str; sort(str.begin(),str.end(),cmp); cout << str << endl; while(next_permutation(str.begin(),str.end(),cmp)){ cout << str << endl; } } return 0; } 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |