交通发达才能发展,农村修路迫不及待。
给出一个函数来输出一个字符串的所有排列。
思路很简单,时间复杂度O(n*n),思路如下(对于还有相同字符的字符串,答案会有重复的,去重就好了)
- 保存一个空的字符串A,
- 对给定字符串B的每一个字符
- 插入A中,出入的位置有n(n为当前字符串A的长度)+1种情况
- 直至A的长度和B相同时,则输出A
举个例子,如下给定字符串string=“bhe”
- 对于三个字符,答案最多就是6个
test.cpp#include <iostream> #include <string> #include <fstream> using namespace std; // function all orders void All_orders(string A,string B,string::size_type n,ofstream &f); // function randstring string RandString(); // function main int main() { int i = 0; while(i<1) { ofstream f; f.open("txt.txt"); string test = RandString(); cout<<"test="<<test<<endl; All_orders("",test,0,f); f.close(); i++; } system("pause"); return 0; } // function all orders void All_orders(string A,string B,string::size_type n,ofstream &f) { if(n < B.length()) { string next = A; next = B[n] + A; All_orders(next,B,n+1,f); for(string::size_type i = 1;i < A.length();i++) { next = A.substr(0,i)+B[n]+A.substr(i,A.length()); All_orders(next,B,n+1,f); } if(A.length()>0) { next = A + B[n]; All_orders(next,B,n+1,f); } } else if(n == B.length()) { cout<<A<<" "<<endl; f<<A<<endl; } } // function randstring string RandString() { int size = 4; string result = ""; for(int i = 0; i<size; i++) { result = result + (char)( ‘a‘ + rand()%10 ); } return result ; }
原文:http://blog.csdn.net/cqs_experiment/article/details/18676369