#include <stdio.h>
#include <iostream>
using namespace std;
#define DIR_LEFT 0
#define DIR_RIGHT 1
#define NO_ACTIVE_NUMBER -1
typedef struct tagNumber
{
int ;
int direction;
} Number;
int findMaximumActiveNumber( Number *a , int n );
int findPPos( Number *a, int n, int p );
void main()
{
int n;
cout << "输入n: ";
cin >> n;
Number *a = new Number[ n ];
FILE *op = fopen( "生成排列.txt", "w" );
for ( int i = 0 ; i < n ; i++ )
{
a[ i ]. = i + 1;
a[ i ].direction = DIR_LEFT;
fprintf( op, "%d", a[i]. );
}
fprintf( op, "\n" );
while( findMaximumActiveNumber( a, n ) != NO_ACTIVE_NUMBER )
{
// 找出最大活动整数
int pos = findMaximumActiveNumber( a, n );
int m = a[ pos ].;
Number hold;
// 交换m和其相邻的整数
if ( a[ pos ].direction == DIR_LEFT && pos != 0 )
{
hold = a[ pos ];
a[ pos ] = a[ pos - 1 ];
a[ pos - 1 ] = hold;
}
else if ( a[ pos ].direction == DIR_RIGHT && pos != n-1 )
{
hold = a[ pos ];
a[ pos ] = a[ pos + 1 ];
a[ pos + 1 ] = hold;
}
// 交换所有p>m的p的方向
if ( m < n )
{
for ( int j = m + 1 ; j <= n ; j++ )
{
int p_pos = findPPos( a, n, j );
if ( a[ p_pos ].direction == DIR_LEFT )
a[ p_pos ].direction = DIR_RIGHT;
else
a[ p_pos ].direction = DIR_LEFT;
}
}
// 输出
for ( i = 0 ; i < n ; i++ )
fprintf( op, "%d", a[i]. );
fprintf( op, "\n" );
}
delete [] a;
}
int findMaximumActiveNumber( Number *a , int n )
{
int i;
int max = NO_ACTIVE_NUMBER;
int max_val = 1;
for ( i = 0 ; i < n ; i++ )
{
if ( i != 0 &&
a[ i ].direction == DIR_LEFT &&
a[ i ]. > a[ i-1 ]. &&
a[ i ]. > max_val )
{
max = i;
max_val = a[ i ].;
}
if ( i != n-1 &&
a[ i ].direction == DIR_RIGHT &&
a[ i ]. > a[ i+1 ]. &&
a[ i ]. > max_val )
{
max = i;
max_val = a[ i ].;
}
}
return max;
}
int findPPos( Number *a, int n, int p )
{
for ( int i = 0 ; i < n ; i++ )
if ( a[ i ]. == p )
return i;
}
|