1

我正在尝试在 C++ 中实现堆的算法。
但是，如果它正在置换的字符串的长度为 4，则该算法开始重复。代码如下：

void permute(int n, string str, int *total,string array[]){

    if (n==0){
        
        array[*total] = str;
        *total += 1;
    
    }

    else{
    
        for(int c=0; c<=n;c++){
            
            permute(n-1,str,total, array);
            if (n % 2 == 0){
                char tmpstr=str[c];
                str[c]=str[n];
                str[n]=tmpstr; 
                }
            else{
                char tmpstr=str[0];
                str[0]=str[n];
                str[n]=tmpstr;
            }
        }
    }
}

int main() {
    int total = 0;
    string array[24];
    permute(3,"abcd",&total, array);
    cout << total << endl;
    return 0;
}

这是输出。它在第 13 行重复

24
abcd
bacd
cbad
bcad
cabd
acbd
dbca
bdca
cbda
bcda
cdba
dcba
abcd <-- right here
bacd
cbad
bcad
cabd
acbd
dbca
bdca
cbda
bcda
cdba
dcba

谢谢你们，欢迎任何帮助！

4

3 回答 3

2

虽然使用 PaulMcKenzie 推荐的标准函数总是一个好主意，但您已经发布了一个代码，其中包含一个关于它为什么不起作用的问题。

在您的 for 循环中，删除该行if (n%2 ==0)及其 else 部分： 

  for(int c=0; c<=n;c++){
        permute(n-1,str,total, array);
        char tmpstr=str[c];
        str[c]=str[n];
        str[n]=tmpstr; 
        }

然后它应该工作。

于 2014-07-16T18:44:23.663 回答
0

看起来您正在尝试实现wikipedia中所述的用于排列生成的 Heap 算法的递归版本，最初在此处给出。如果您想靠近它（例如，在生成排列时具有相同的顺序），您所要做的就是将str参数作为参考传递（您必须更改调用permute()函数的行以传递可变字符串而不是字符串常量，强硬）并在程序中保留 if-then-else 子句。

不过，@Christophe 给出的版本很有趣。我已经尝试了最多n=6（7个元素的排列），并且仍然给出了所有排列。知道这是否可以证明适用于任何自然数会很有趣。然而，这一点可能没有实际意义，因为我引用的两个参考文献中给出的递归版本也没有实现 Heap 给出的原始版本，而且据我所知，也没有被证明可以给出所有排列。Heap 给出的原始版本写于 1963 年，甚至没有使用结构化编程。它以流程图的形式给出，用goto's 来实现。

于 2015-02-23T14:16:45.733 回答
0

在这里，有我的递归和迭代版本的实现：

//recursive
int perm_num = 0;
void heappermute(int v[], int n) {
    int i;
    if (n == 1) {
        //print(v);
        ++perm_num;
    }
    else {
        for (i = 0; i < n; i++) {
            heappermute(v, n - 1);

            if (n % 2 == 1) {
                swap(&v[0], &v[n - 1]);
            }
            else {
                swap(&v[i], &v[n - 1]);
            }
        }
    }
}

int perm_num_iter = 0;
void heappermuteiterative(int v[], int n) {
    int c[30];
    for (int i = 0; i <= n; ++i) {
        c[i] = 0;
    }

    ++perm_num_iter;
    //print(v);

    int i = 1;
    while (i < n) {
        if (c[i] < i) {
            if (i % 2 == 0) {
                swap(&v[0], &v[i]); // or i-1
            }
            else {
                swap(&v[c[i]], &v[i]); // or i-1
            }

            ++perm_num_iter;
            //print(v);

            ++c[i];
            i = 1;
        }
        else {
            c[i] = 0;
            ++i;
        }
    }
}

我从网上的某个地方复制了递归的，迭代的是维基百科用 C 编写的。

于 2021-10-19T12:58:32.420 回答