Knuth置换算法奇怪的行为

Question

我附上了一个代码，它给出了基于cout语句的奇怪输出。这个程序基本上计算Knuth的排列。

输入是说：RUN1 代码为第一遍运行良好： 呼叫跟踪将是：
[R UN1
乌尔N1
淖尔1
1nur
n1ur
nu1r
nur1
在这段代码运行之后，呼叫正确返回到步骤
urn 1
在那里，但它没有在“R ETURN“声明。

此外，如果是假设，其中置换完成循环内的COUT，它不连打印return语句下面的COUT

请让我知道是否有在我的代码或逻辑的任何根本的缺陷错误？

#include <iostream> 
using namespace std; 

void swap(char *l, char *m) 
{ 
char t = *l; 
*l = *m; 
*m = t; 
} 
void Permute(char *result, char *temp, int len) 
{ 
int k = 0; 
int j = 0; 
char d[ 1000000]; 
int i = 0; 
//cout << " Start of Perm " << result << " Stack: " << temp << endl; 
while(result[ i ] != '\0') 
{ 
    if(temp[ k ] !='\0') 
    { 
    cout << " Start of Perm " << result << " Stack: " << temp << endl; 
    strncpy(d, &temp[ k ], sizeof(char)); 
    strncat(d, result, sizeof(result) ); 
    strncat(d, "\0", sizeof(char)); 
    cout << " Principal: " << d << endl; 
    k = k + 1; 
    if(temp[ k ] != '\0') 
    Permute(d, &temp[ k ], len); 
    else 
    { 
    char d1[ 10000 ]; 
    strncpy(d1, &temp[ k ], sizeof(char)); 
    strncat(d1, d, sizeof(d) ); 
    strncat(d, "\0", sizeof(char)); 
    strncpy(d, d1, sizeof(d)); 
    //cout << "Final Level: " << d << endl; 
    strncpy(result, d, sizeof(d)); 
    } 
    } 
    //cout << strlen(result) << " == length which is " << len << " and result is: " << result << endl; 
    if(strlen(result) >= len) 
    { 
    //cout << " Permutation Sets" << endl; 
    char result1[ 1000 ]; 
    memcpy(result1, result, sizeof(result)); 
    for(int p = 0; result1[ p ] != '\0'; p++) 
    { 
    cout << "End : " << result1 << endl; 
    if(result1[ p + 1 ] != '\0') 
    swap(&result1[ p ], &result1[ p + 1 ]); 
    } 
    return; 
    } 
    cout << " Value of I is: " << i << " and value of K is: " << k << endl; 
    if(result[ i + 1 ] != '\0') 
    { 
    swap(&result[ i ], &result[ i + 1 ]); 
    k = 0; 
    d[ 0 ] = '\0'; 
    cout << "New Branch: Value = " << result << " and stack = " << temp << endl; 
    } 
    i = i + 1; 
} 
} 



int main(int argc, char *argv[]) 
{ 
char c[100], temp[100]; 
cin >> c; 
// cout << c << endl; 
memcpy(temp, c, sizeof(c)); 
// cout << temp << endl; 
char c1[2]; 
c1[0] = c[0]; 
c1[1] = '\0'; 
Permute(c1, &temp[1], strlen(c)); 
} 

谢谢！

Answer 1

使用像gdb这样的调试器，逐行执行程序，同时检查值。

Answer 2

对于C++，您应该在<string>标头中使用string类。这将使你的代码更安全，更好的可读性。也许你可以更好地发现你的错误。

Answer 3

如果这不是用于个人教育，你应该使用预定义功能next_permutation。这是很容易使用：

#include <algorithm> 
#include <iostream> 
#include <string> 

using std::string; 
using std::cout; 
using std::sort; 

int main() { 
    string s("run1"); 

    sort(s.begin(), s.end()); 

    do { 
    cout << s << "\n"; 
    } while (next_permutation(s.begin(), s.end())); 

    return 0; 
} 

如果你真的需要与run1开始排列，你仍然可以生成vector<int>的排列包含{0, 1, 2, 3}，然后通过这个代码构建中间字符串：

#include <algorithm> 
#include <cstddef> 
#include <iostream> 
#include <string> 
#include <vector> 

using std::cout; 
using std::string; 
using std::vector; 

int main() { 
    string s("run1"); 

    vector<int> indexes; 
    for (size_t i = 0; i < s.size(); i++) 
    indexes.push_back(i); 

    do { 
    string tmp(""); 
    for (size_t i = 0; i < indexes.size(); i++) 
     tmp += s[indexes[i]]; 
    cout << tmp << "\n"; 
    } while (next_permutation(indexes.begin(), indexes.end())); 

    return 0; 
}