为了求出一个数的全排列的所有组合,此处我用到了哈密尔顿图的遍历算法,有些笨拙,不知道有没有更好的算法,敬请指教。
#define NUM 128
typedef struct
{
int vex[NUM]; /* 图中的顶点 */
int arcs[NUM][NUM]; /* 图中的边 */
int vexnum,arcnum; /* 顶点数,边数 */
}MGraph; /* 定义图的类型 */
MGraph G; /* 把图定义为全局变量 */
int x[NUM]={0}; /* 标志数组 */
int m_number;
int sum = 0;
void CreateUDN(int v,int a); /* 造图函数 */
void HaMiTonian(int); /* 哈密尔顿图的遍历 */
void NextValue(int);
void display(); /* 显示遍历结果 */
void main()
{
system("color fc");
printf("输入全排列的数字:");
scanf("%d",&m_number);
CreateUDN(m_number,m_number);
x[1]=1;
HaMiTonian(0);
printf("/n%d的全排列总共的组合数有%d种。", m_number, sum);
system("pause");
}
void CreateUDN( int v, int a ) /* 造图函数 */
{
int i,j;
G.vexnum = v; /* 初始化图的顶点数和边数 */
G.arcnum = a;
for( i=0; i < G.vexnum; i++ )
{
G.vex[i] = i + 1; /* 初始化每一个顶点的编号 */
}
for( i=0; i < G.vexnum; i++ ) /* 设置为全连通图 */
{
for( j = 0; j < G.vexnum; j++)
{
G.arcs[i][j] = 1;
}
}
}
void HaMiTonian( int m ) /* 哈密尔顿图的遍历 */
{
if( m > m_number - 1 )
{
return;
}
L: NextValue( m );
if( 0 == x[m] )
{
return;
}
if( (m == m_number - 1) && (0 != G.arcs[0][x[m_number-1] - 1]) )
{
display();
}
else
{
HaMiTonian( m + 1 );
}
goto L;
}
void NextValue( int k )
{
int j;
l:x[k] = (x[k] + 1) % (m_number + 1);
if( 0 == x[k] )
{
return;
}
if( 0 != G.arcs[x[k-1] -1 ][x[k] - 1] )
{
for( j = 0; j < k; j++ )
{
if( x[j] == x[k] )
{
goto l;
}
}
return;
}
else
{
goto l;
}
}
void display()
{
int i = 0;
int m_array[NUM];
FILE *fp = fopen( "Result.txt", "a+" );
if( fp )
{
for( i = 0; i < m_number; i++ )
{
printf( "%d", G.vex[x[i] - 1] );
fprintf( fp, "%d", G.vex[x[i] - 1] );
m_array[i] = G.vex[x[i] - 1];
}
sum ++;
printf("/n");
fprintf( fp, "/n");
//if( m_array[0] < m_array[3] && m_array[1] < m_array[4] && m_array[3] < m_array[5] )
//{
// for( i = 0; i < m_number; i++ )
// {
// printf( "%d", m_array[i] );
// }
// printf(" ");
//}
fclose(fp);
}
}