有没有更好的方法来执行字符串的排列？ [英] Are there any better methods to do permutation of 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] 作为稳步preFIX和海峡[mid..end] 作为置换后缀）。因此，我们可以使用置换（STR，0，str.size（） - 1）。显示一个字符串的所有排列

The above function shows the permutations of str(with str[0..mid-1] as a steady prefix, and str[mid..end] as a permutable suffix). So we can use permute(str, 0, str.size() - 1) to show all the permutations of one string.

不过，该函数使用递归算法;也许它的性能还有待改进？

But the function uses a recursive algorithm; maybe its performance could be improved?

有没有更好的方法来重排一个字符串？

Are there any better methods to permute a string?

推荐答案

下面是来自于的无序一代排列的。对于字符串取值长度 N ，对于任何 K 从 0 到 N！ - 1 包容，以下修改取值来提供一个独特的置换（即从那些其他K值产生在该范围内的不同） 。要生成所有排列，运行它对于所有的n！ K 值对s的原始值。

Here is a non-recursive algorithm in C++ from the Wikipedia entry for unordered generation of permutations. For the string s of length n, for any k from 0 to n! - 1 inclusive, the following modifies s to provide a unique permutation (that is, different from those generated for any other k value on that range). To generate all permutations, run it for all n! k values on the original value of s.

#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);
    }
}

下面互换（S，I，J）交换位置，我和字符串的Sj。

Here swap(s, i, j) swaps position i and j of the string s.

这篇关于有没有更好的方法来执行字符串的排列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！