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]
作为可置换后缀)。因此,我们可以使用permute(str, 0, str.size() - 1)
显示一个字符串的所有排列。但是该函数使用递归算法;也许它的性能可以提高?
有没有更好的方法来置换字符串?
最佳答案
这是Wikipedia条目中unordered generation of permutations的C++非递归算法。对于长度为s
的字符串n
,对于从k
到0
(包括首尾)的任何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)
交换字符串s的位置i和j。关于c++ - 有没有更好的方法来对字符串进行排列?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/1995328/