有没有更好的方法来排列string？
void permute(string elems, int mid, int end) { static int count; if (mid == end) { cout << ++count << " : " << elems << endl; return ; } else { for (int i = mid; i <= end; i++) { swap(elems, mid, i); permute(elems, mid + 1, end); swap(elems, mid, i); } } } 上面的函数显示了str （ str[0..mid-1]作为一个稳定的前缀， str[mid..end]作为一个可置换的后缀）的str[mid..end] 。 所以我们可以使用permute(str, 0, str.size() - 1)来显示一个string的所有排列。
但是函数使用recursionalgorithm; 也许它的performance可以改善？
有没有更好的方法来排列string？
这是C ++中的一个非recursionalgorithm，来自维基百科条目，用于无序生成排列 。 对于长度为n的strings ，对于从0到n! - 1任何k n! - 1 n! - 1包括在内，以下修改s以提供唯一的排列（即，与那个范围内的任何其他k值产生的排列不同）。 要生成所有的排列，请运行它的所有n！ 关于s的原始值的k值。
#include <algorithm> void permutation(int k, string &s) { for(int j = 1; j < s.size(); ++j) { std::swap(s[k % (j + 1)], s[j]); k = k / (j + 1); } }
这里swap(s, i, j)交换位置i和j的strings。
为什么不试试std::next_permutation()或std::prev_permutation() ？
链接：
的std :: next_permutation（）
的std :: prev_permutation（）
一个简单的例子：
#include<string> #include<iostream> #include<algorithm> int main() { std::string s="123"; do { std::cout<<s<<std::endl; }while(std::next_permutation(s.begin(),s.end())); }
输出：
123 132 213 231 312 321
我想第二个Permaquid的答案 。 他引用的algorithm与已经提供的各种排列枚举algorithm有着根本不同的方式。 它不会生成所有n个对象的排列，它会生成一个不同的特定排列，给定一个介于0 and n!-1之间的整数。 如果你只需要一个特定的排列，比列举全部然后select一个更快。
即使你确实需要所有的排列，它也提供了一个排列枚举algorithm没有的选项。 我曾经写过一个蛮力的cryptarithm cracker，试图把每个可能的字母分配给数字。 对于base-10问题，这是足够的，因为只有10! 排列尝试。 但是对于base-11问题花了几分钟， base-12问题花了近一个小时。
我使用Permaquid引用的algorithm，用简单的i=0--to--N-1 for-loopreplace了我一直使用的排列枚举algorithm。 结果只是稍微慢一点。 但是接下来我将整数范围分为四个部分，并同时运行四个for-loops，每个都在一个单独的线程中。 在我的四核处理器上，所产生的程序运行速度几乎快了四倍。
就像使用排列枚举algorithmfind一个单独的排列是困难的，产生所有排列集合的划定的子集也是困难的。 Permaquid引用的algorithm使得这两个都非常简单
特别是，你想要std :: next_permutation 。
void permute(string elems, int mid, int end) { int count = 0; while(next_permutation(elems.begin()+mid, elems.end())) cout << << ++count << " : " << elems << endl; }
… 或类似的东西…
生成置换的任何algorithm都将在多项式时间内运行，因为n长度string内字符的排列数是(n!) 。 也就是说，有一些非常简单的就地生成排列algorithm。 检查Johnson-Trotteralgorithm 。
Knuth随机洗牌algorithm值得研究。
// In-place shuffle of char array void shuffle(char array[], int n) { for ( ; n > 1; n--) { // Pick a random element to move to the end int k = rand() % n; // 0 <= k <= n-1 // Simple swap of variables char tmp = array[k]; array[k] = array[n-1]; array[n-1] = tmp; } }
任何使用或产生所有排列的algorithm都会花费O（N！* N）时间，O（N！）至less产生所有排列，而O（N）使用结果，这真的很慢。 请注意，打印string也是O（N）afaik。
不pipe你用什么方法，在一秒钟内，你只能处理最多10或11个字符的string。 由于11 * 11 = 439084800次迭代（在大多数机器上这么做的时间很多，所以这样做）和12！* 12 = 5748019200次迭代。 所以即使是最快的实现也需要12到12个字符，大约需要30到60秒。
阶乘的增长速度太快了，希望通过编写一个更快的实现来获得任何东西，最多只能获得一个字符。 所以我build议Prasoon的build议。 编码很简单，而且速度很快。 虽然坚持你的代码也是完全好的。
我只是build议你小心一点，你不要在你的string中多余的字符，比如空字符。 因为这会使你的代码变慢N倍。
我最近写了一个排列algorithm。 它使用T（模板）types的向量而不是string，它不是超快的，因为它使用了recursion并且有很多复制。 但也许你可以从代码中得到一些启发。 你可以在这里find代码。
显着提高性能的唯一方法就是find一种方法来避免首先对所有排列进行迭代！
排列是一个不可避免的缓慢的操作（O（n！），或者更糟，取决于你对每个排列做什么），遗憾的是，你所能做的任何事情都不会改变这个事实。
另外，请注意，任何现代编译器都会在优化启用时将recursion展平，因此手优化的（小）性能收益会进一步降低。
你想通过所有的排列，或计数排列的数量？
对于前者，按照其他人的build议使用std::next_permutation 。 每个置换都需要O（N）个时间（但是分摊时间更less），除了调用帧外，没有内存，而recursion函数的O（N）时间和O（N）内存。 正如其他人所说的，整个过程是O（N！），你不能做得比这更好，因为在小于O（X）的时间内你不能得到比O（X）更多的结果。 没有量子计算机，无论如何。
对于后者，你只需要知道string中有多less个独特的元素。
big_int count_permutations( string s ) { big_int divisor = 1; sort( s.begin(), s.end() ); for ( string::iterator pen = s.begin(); pen != s.end(); ) { size_t cnt = 0; char value = * pen; while ( pen != s.end() && * pen == value ) ++ cnt, ++ pen; divisor *= big_int::factorial( cnt ); } return big_int::factorial( s.size() ) / divisor; }
速度受到查找重复元素的操作的限制，对于char可以在O（N）时间内用查找表完成。
我不认为这是更好的，但它确实工作，不使用recursion：
#include <iostream> #include <stdexcept> #include <tr1/cstdint> ::std::uint64_t fact(unsigned int v) { ::std::uint64_t output = 1; for (unsigned int i = 2; i <= v; ++i) { output *= i; } return output; } void permute(const ::std::string &s) { using ::std::cout; using ::std::uint64_t; typedef ::std::string::size_type size_t; static unsigned int max_size = 20; // 21! > 2^64 const size_t strsize = s.size(); if (strsize > max_size) { throw ::std::overflow_error("This function can only permute strings of size 20 or less."); } else if (strsize < 1) { return; } else if (strsize == 1) { cout << "0 : " << s << '\n'; } else { const uint64_t num_perms = fact(s.size()); // Go through each permutation one-by-one for (uint64_t perm = 0; perm < num_perms; ++perm) { // The indexes of the original characters in the new permutation size_t idxs[max_size]; // The indexes of the original characters in the new permutation in // terms of the list remaining after the first n characters are pulled // out. size_t residuals[max_size]; // We use div to pull our permutation number apart into a set of // indexes. This holds what's left of the permutation number. uint64_t permleft = perm; // For a given permutation figure out which character from the original // goes in each slot in the new permutation. We start assuming that // any character could go in any slot, then narrow it down to the // remaining characters with each step. for (unsigned int i = strsize; i > 0; permleft /= i, --i) { uint64_t taken_char = permleft % i; residuals[strsize - i] = taken_char; // Translate indexes in terms of the list of remaining characters // into indexes in terms of the original string. for (unsigned int o = (strsize - i); o > 0; --o) { if (taken_char >= residuals[o - 1]) { ++taken_char; } } idxs[strsize - i] = taken_char; } cout << perm << " : "; for (unsigned int i = 0; i < strsize; ++i) { cout << s[idxs[i]]; } cout << '\n'; } } }
有趣的是，它从排列到排列使用的唯一状态是排列数，排列总数和原始string。 这意味着它可以很容易地封装在一个迭代器或类似的东西，而不必仔细保留确切的正确的状态。 它甚至可以是一个随机访问迭代器。
当然:: std :: next_permutation将状态存储在元素之间的关系中，但是这意味着它不能在无序的事情上工作，而且如果在序列中有两个相同的东西，我真的不知道它会发生什么。 你当然可以通过排列索引来解决这个问题，但是这会增加一些复杂性。
如果它足够短，我的任何随机访问迭代器都可以工作。 如果不是的话，无论如何你都不可能完成所有的排列。
该algorithm的基本思想是可以枚举N个项的每一个置换。 总数是N！ 或fact(N) 。 任何给定的排列可以被认为是源序列从原始序列到新序列中的一组目标序列的映射。 一旦你列举了所有的排列，唯一剩下要做的就是把每个排列的数字映射成一个实际的排列。
排列列表中的第一个元素可以是原始列表中的N个元素中的任何一个。 第二个元素可以是其余N-1个元素中的任何一个，依此类推。 该algorithm使用%运算符将排列数分解为一组具有这种性质的select。 首先用N取模的排列数为[0，N]。 通过除以N除去余数，然后以列表-1的大小对其进行模数化，得到[0，N-1]中的一个数字，依此类推。 这就是for (i =循环正在做的事情。
第二步是将每个数字转换为原始列表中的索引。 第一个数字很简单，因为它只是一个直接的索引。 第二个数字是一个列表中的索引，包含除第一个索引处被删除的元素之外的所有元素，以此类推。 这就是for (o =循环正在做的事情。
residuals是连续较小列表中的索引列表。 idxs是原始列表中的索引列表。 residuals和idxs之间有一对一的映射。 它们在不同的“坐标空间”中代表相同的值。
你select的答案指出的答案具有相同的基本思想，但是比我的文字和蛮力方法有更完美的方法来完成映射。 这样比我的方法稍微快一些，但它们的速度都是相同的，它们都具有随机访问置换空间的相同优势，这使得整个事情变得更加容易，包括（正如您挑选的答案所指出的那样）并行algorithm。
其实你可以用Knuth混洗algorithm来做！
// find all the permutations of a string // using Knuth radnom shuffling algorithm! #include <iostream> #include <string> template <typename T, class Func> void permutation(T array, std::size_t N, Func func) { func(array); for (std::size_t n = N-1; n > 0; --n) { for (std::size_t k = 0; k <= n; ++k) { if (array[k] == array[n]) continue; using std::swap; swap(array[k], array[n]); func(array); } } } int main() { while (std::cin.good()) { std::string str; std::cin >> str; permutation(str, str.length(), [](std::string const &s){ std::cout << s << std::endl; }); } }
这篇文章： http ： //cplusplus.co.il/2009/11/14/enumerating-permutations/处理几乎任何东西，不仅string。 post本身和下面的评论是相当丰富的，我不想复制和粘贴..
如果你对排列生成感兴趣，我在一段时间后做了一个研究论文： http : //www.oriontransfer.co.nz/research/permutation-generation
它带有完整的源代码，并且有5种左右的不同的实现方法。
//***************anagrams**************// //************************************** this code works only when there are no repeatations in the original string*************// #include<iostream> using namespace std; int counter=0; void print(char empty[],int size) { for(int i=0;i<size;i++) { cout<<empty[i]; } cout<<endl; } void makecombination(char original[],char empty[],char comb[],int k,int& nc,int size) { nc=0; int flag=0; for(int i=0;i<size;i++) { flag=0; // { for(int j=0;j<k;j++) { if(empty[j]==original[i]) // remove this code fragment { // to print permutations with repeatation flag=1; break; } } if(flag==0) // } { comb[nc++]=original[i]; } } //cout<<"checks "; // print(comb,nc); } void recurse(char original[],char empty[],int k,int size) { char *comb=new char[size]; int nc; if(k==size) { counter++; print(empty,size); //cout<<counter<<endl; } else { makecombination(original,empty,comb,k,nc,size); k=k+1; for(int i=0;i<nc;i++) { empty[k-1]=comb[i]; cout<<"k = "<<k<<" nc = "<<nc<<" empty[k-1] = "<<empty[k-1]<<endl;//checks the value of k , nc, empty[k-1] for proper understanding recurse(original,empty,k,size); } } } int main() { const int size=3; int k=0; char original[]="ABC"; char empty[size]; for(int f=0;f<size;f++) empty[f]='*'; recurse(original,empty,k,size); cout<<endl<<counter<<endl; return 0; }
即使我发现很难理解第一次的recursion版本，并花了一些时间来寻找berre的方式。find（我能想到）的更好的方法是使用Narayana Pandita提出的algorithm。 基本的想法是：
- 首先按照非递减的顺序对给定的string进行sorting，然后从末尾find小于下一个字符的第一个元素的索引。 调用这个元素索引'firstIndex'。
- 现在find“firstIndex”上元素的最小字符。 调用这个元素索引'ceilIndex'。
- 现在在'firstIndex'和'ceilIndex'交换元素。
- 颠倒从索引'firstIndex + 1'开始的string部分到string结尾。
- （而不是第4点）也可以将索引'firstIndex + 1'中的部分stringsorting到string的末尾。
第4点和第5点做同样的事情，但是第4点的时间复杂度是O（n * n！），第5点的情况是O（n ^ 2 * n！）。
上述algorithm甚至可以应用于string中有重复字符的情况。 ：
显示string的所有排列的代码：
#include <iostream> using namespace std; void swap(char *a, char *b) { char tmp = *a; *a = *b; *b = tmp; } int partition(char arr[], int start, int end) { int x = arr[end]; int i = start - 1; for(int j = start; j <= end-1; j++) { if(arr[j] <= x) { i = i + 1; swap(&arr[i], &arr[j]); } } swap(&arr[i+1], &arr[end]); return i+1; } void quickSort(char arr[], int start, int end) { if(start<end) { int q = partition(arr, start, end); quickSort(arr, start, q-1); quickSort(arr, q+1, end); } } int findCeilIndex(char *str, int firstIndex, int n) { int ceilIndex; ceilIndex = firstIndex+1; for (int i = ceilIndex+1; i < n; i++) { if(str[i] >= str[firstIndex] && str[i] <= str[ceilIndex]) ceilIndex = i; } return ceilIndex; } void reverse(char *str, int start, int end) { while(start<=end) { char tmp = str[start]; str[start] = str[end]; str[end] = tmp; start++; end--; } } void permutate(char *str, int n) { quickSort(str, 0, n-1); cout << str << endl; bool done = false; while(!done) { int firstIndex; for(firstIndex = n-2; firstIndex >=0; firstIndex--) { if(str[firstIndex] < str[firstIndex+1]) break; } if(firstIndex<0) done = true; if(!done) { int ceilIndex; ceilIndex = findCeilIndex(str, firstIndex, n); swap(&str[firstIndex], &str[ceilIndex]); reverse(str, firstIndex+1, n-1); cout << str << endl; } } } int main() { char str[] = "mmd"; permutate(str, 3); return 0; }
这是我刚刚沙沙作响的！
void permute(const char* str, int level=0, bool print=true) { if (print) std::cout << str << std::endl; char temp[30]; for (int i = level; i<strlen(str); i++) { strcpy(temp, str); temp[level] = str[i]; temp[i] = str[level]; permute(temp, level+1, level!=i); } } int main() { permute("1234"); return 0; }
这不是最好的逻辑，但是，我是一个初学者。 如果有人给我这个代码的build议，我会很高兴和责任
#include<iostream.h> #include<conio.h> #include<string.h> int c=1,j=1; int fact(int p,int l) { int f=1; for(j=1;j<=l;j++) { f=f*j; if(f==p) return 1; } return 0; } void rev(char *a,int q) { int l=strlen(a); int m=lq; char t; for(int x=m,y=0;x<q/2+m;x++,y++) { t=a[x]; a[x]=a[ly-1]; a[ly-1]=t; } c++; cout<<a<<" "; } int perm(char *a,int f,int cd) { if(c!=f) { int l=strlen(a); rev(a,2); cd++; if(c==f)return 0; if(cd*2==6) { for(int i=1;i<=c;i++) { if(fact(c/i,l)==1) { rev(a,j+1); rev(a,2); break; } } cd=1; } rev(a,3); perm(a,f,cd); } return 0; } void main() { clrscr(); char *a; cout<<"\n\tEnter a Word"; cin>>a; int f=1; for(int o=1;o<=strlen(a);o++) f=f*o; perm(a,f,0); getch(); }
