shenlaners

刚学组合数学,实现了字典序求全排列的算法和组合算法．
程序写的很粗糙，欢迎与我讨论．qq:305351190
////////////////////////////////////////////////////////////////////////////////////////////
//排列,测试函数略
void   print(int   *x,int   n)   
//自定义执行函数   
{   
for(int   i=1;i<=n;i++)   
  printf("%4d",x);   
printf("\n");   
}   
void perm2( int n )
//n个元素的全排列（字典序法）
{
int *a = new int[n+1];
int k,s,t;
k = s = 0;
a[0] = 0;
if (n > 1) //元素个数必须大于1
{
  for ( int j = 1; j < n + 1; j ++ )
   a[j] = a[j-1] + 1; //初始化排列为1,2,3,...,n
  print( a, n ); //打印一组排列
  j = 0;
  while ( j < n )
  {
   //求下一组排列
   for ( int i = 2; i < n + 1; i ++ )
    if ( a[i-1] < a )
     k = i;
    a[0] = a[k-1];
   for ( i = 1; i < n + 1; i ++ )
    if ( a[0] < a )
     s = i;
   a[k-1] = a[s];
   a[s] = a[0];
   t = n;
   for ( i = k; i < (int)((n - k + 1) / 2) + k; i ++ )
   {
    a[0] = a;
    a = a[t];
    a[t] = a[0];
    t --;
   }
   print( a, n );//打印
   //判断排列是否求完
   for ( j = 1; j < n; j ++ )
    if ( a[j] < a[j+1] )
     break;
  }
}
delete a;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////
//求组合要比排列容易
#include "stdio.h"
void combination( int *a, int *b, int n, int m );
void print( int *b, int n );
int get_nextcob( int *b, int n, int m );
void main ()
{
int *a, *b;
a = new int[11];
b = new int[3];
for ( int i = 1; i < 11; i ++ )
  a = i;
combination( a, b, 10, 10);
}
void combination( int *a, int *b, int n, int m )
// 求从数组a的n个元素中取m个元素的组合
{
int f;
f = 0;
if ( n < m )
{
  printf("m太大！");
  return;
}
// 初始化数组b
for ( int i = 1; i < m+1; i ++ )
  b = a;
print( b, m );
while( 1 )
{
  if ( get_nextcob( b, n, m ) == 0 )
   break;
  print( b, m );
}
}
void print( int *b, int m )
{
for ( int i = 1; i < m + 1; i++ )
  printf( "%4d" , b );
printf("\n");
}
int get_nextcob( int *b, int n, int m )
{
int f;
f = 0;
for ( int i = 1; i < m + 1; i ++ )
  if ( b < n - m + i )
   f = i;
if ( f == 0 )
  return 0;
b[0] = b[f];
b[f] = b[f] + 1;
for (i = f + 1; i < m + 1; i ++ )
  b = b[i-1] + 1;
return 1;
}

[ 本帖最后由 shenlaners 于 2007-9-20 21:46 编辑 ]