Knuth Permutation Algorithm Comportement bizarre

Question

J'ai joint un code qui donne des sorties bizarres basées sur des instructions cout. Ce programme calcule essentiellement les permutations de Knuth.

entrée est dit: run1 Le code est exécuté pour la première passe bien: trace d'appel sera:
r un1
ur n1
nur 1
1nur
n1ur
nu1r
nur1
Après cette course de code, l'appel retourne correctement à l'étape où
urn 1
est là mais il ne traite pas le code ci-dessous le "R ETURN "déclaration.

De plus, si on suppose un Cout dans la boucle où les permutations sont faites, il ne marche pas même imprimer le Cout ci-dessous la déclaration de retour

S'il vous plaît laissez-moi savoir s'il y a un défaut fondamental dans mon code ou une logique punaise ?

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

Merci!

Answer 1

Utilisez un débogueur comme gdb et parcourez le programme ligne par ligne, tout en vérifiant les valeurs.

Answer 2

Pour C++, vous devez utiliser la classe string dans l'en-tête <string>. Cela rendra votre code beaucoup plus sûr et mieux lisible. Peut-être que vous pouvez mieux repérer vos erreurs alors.

Answer 3

Si ce n'est pas pour l'éducation personnelle, vous devriez vraiment utiliser la fonction prédéfinie next_permutation. Il est très facile à utiliser:

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

Et si vous avez vraiment besoin de commencer les permutations avec run1, vous pouvez toujours générer les permutations du vector<int> contenant {0, 1, 2, 3}, puis construire la chaîne intermédiaire par ce code:

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