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,对于从k0(包括首尾)的任何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/

10-13 05:21
查看更多