有没有更好的方法来对字符串进行排列？

一尘不染

有没有更好的方法来对字符串进行排列？

algorithm

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)用来显示一个字符串的所有排列。

但是该函数使用递归算法；也许它的性能可以提高？

有没有更好的方法来置换字符串？

阅读 173

2020-07-28

共1个答案

一尘不染

这是Wikipedia条目中C
++中的一种非递归算法，用于无序生成排列。对于slength
的字符串n，对于k从from 0到n! - 1inclusive的任何字符串，以下内容都会进行修改s以提供唯一的排列（即，与为该范围内的任何其他k值生成的排列不同）。要生成所有排列，请对所有n运行它！ks的原始值上的值。

#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。

2020-07-28