学步园

        为了求出一个数的全排列的所有组合，此处我用到了哈密尔顿图的遍历算法，有些笨拙，不知道有没有更好的算法，敬请指教。

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