Knuth Permutation Algorithm Weird behaviour

Question

Hi All,

I have attached a code which gives weird outputs basing on cout statements. This program essentially computes the Knuth's Permutations.

Input is say: run1 The code runs for first pass fine: Call trace will be:
r un1
ur n1
nur 1
1nur
n1ur
nu1r
nur1
After this run of code, the call returns correctly to step where
urn 1
is there but it doesnt proceess the code below the "RETURN" statement.

Also, if there is suppose a cout within the loop where permutations are done, it doesnt even print the cout below the return statement

Please let me know if there is any fundamental flaw in my code or a logical bug ?

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

Thanks!

Answer 1

Use a debugger like gdb and step through the program line by line, while checking the values.

Answer 2

For C++ you should use string class in the <string> header. This will make your code much safer and better readable. Maybe you can spot your errors better then.

Answer 3

If this isn't for personal education, you should really use the predefined function next_permutation. It's quite easy to use:

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

And if you really need to start the permutations with run1, you can still generate the permutations of the vector<int> containing {0, 1, 2, 3} and then build the intermediate string by this 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;
}