Алгоритм перестановки Кнута Странное поведение

Я приложил код, который дает странные результаты на основе операторов cout. Эта программа по существу вычисляет перестановки Кнута.

Ввод: run1 Код выполняется для первого прохода: Трассировка вызова будет:
r un1
ur n1
nur 1
1nur
n1ur
nu1r
nur1 < br> После этого выполнения кода вызов корректно возвращается к шагу,
где присутствует urn 1
, но не обрабатывает код, следующий за оператором "RETURN".

Кроме того, если в цикле, где выполняются перестановки, есть cout, он даже не печатает cout под оператором return.

Пожалуйста, дайте мне знать, есть ли в моем коде какой-либо фундаментальный недостаток или логическая ошибка?

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

Спасибо!


c++ permutation knuth
person RMR    schedule 23.06.2010    source источник
comment
Лучшее описание того, что он должен выводить и что он действительно выводит, было бы полезно.   -  person Adam Crume    schedule 23.06.2010
comment
Предоставьте информацию о поведении, которое вы видите, и о том, что вы на самом деле ожидаете. В нынешнем виде это не вопрос, и, вероятно, он будет закрыт (пожалуйста, просмотрите мой код, это не вопрос, извините).   -  person Binary Worrier    schedule 23.06.2010
comment
Ввод: run1 Код выполняется для первого прохода. Трассировка вызова будет следующей: r un1 ur n1 nur 1 1nur 1nur n1ur nu1r nur1 После последнего набора вызов правильно возвращается к шагу, где urn 1 присутствует, но не обрабатывает вещи ниже оператора RETURN.   -  person RMR    schedule 23.06.2010
comment
Кроме того, если в цикле, где выполняются перестановки, есть cout, он даже не печатает cout под оператором return.   -  person RMR    schedule 23.06.2010
comment
Отредактируйте свой вопрос вместо того, чтобы расширять его в комментариях. Может быть, это интересно, но ваше форматирование затмит содержимое.   -  person miku    schedule 23.06.2010
comment
Можете ли вы сказать мне, о каком алгоритме вы говорите, это алгоритм p (простые изменения)? может помочь   -  person Ramadheer Singh    schedule 11.07.2011

Ответы (3)


arrow_upward
2
arrow_downward

Если это не для личного обучения, вам действительно следует использовать предопределенную функцию 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;
}
person Roland Illig    schedule 28.07.2010
comment
Если вы хотите начать и закончить с run1, не проверяйте, возвращает ли next_permutation false, а проверяйте начальное значение. т.е. do { .... ; next_permuation(s.begin(), s.end()); } while (s != "run1"); - person MSalters; 28.07.2010

arrow_upward
1
arrow_downward

Используйте отладчик, такой как gdb, и выполняйте программу строка за строкой, проверяя значения.

person Sjoerd    schedule 23.06.2010

arrow_upward
1
arrow_downward

Для C++ вы должны использовать класс string в заголовке <string>. Это сделает ваш код более безопасным и читабельным. Может быть, тогда вы сможете лучше замечать свои ошибки.

person codymanix    schedule 23.06.2010