输出一个数全排列的组合【利用哈密尔顿图遍历算法实现】

68 阅读 0 评论 45 点赞

我是靠谱客的博主健忘日记本，最近开发中收集的这篇文章主要介绍输出一个数全排列的组合【利用哈密尔顿图遍历算法实现】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

#include <string.h> #include <stdio.h> #include <stdlib.h> #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); } }