一个排列、组合的生成算法

给定数字1～n，输出从中选出m个数的排列和组合。

为了简单起见，采用递归算法来描述，首先解决排列问题：

这个算法不太漂亮，用到了两个全局变量：

int ARR[] = { 1,2,3,4,5}; // 用来输出的全局缓冲区

int PERM_LEN; // 排列的长度

void permutation( int arr[], int n, int m )

{

int i;

if( m== 0 )

{

for(i=0;i<PERM_LEN;++i)

printf(" %d",ARR[i]);

printf("\n");

return;

}

for(i=0; i<n; ++i)

{

swap( arr[i], arr[0] );

permutation( arr+1, n-1, m-1 );

swap( arr[i], arr[0] );

}

}

算法比较简单，不详细说明了。

组合算法比较有趣，先看99年左右的高程辅导书上的解法，

这里面使用了一个全局变量，用来控制输出宽度：

int k; // 用来控制输出宽度的全局变量，注意取值为组合的宽度r

void comb2( int n,int r)

{

int i;

for( i=n;i>=r;i--)

{

if( i!=n && k!=r )

{

int temp ;

for( temp =1; temp<=(k-r)*3;temp++)

printf(" ");

}

printf("%3d",i);

if( r> 1 )

comb2( i-1, r-1 );

else

printf("\n");

}

}

原理也很简单，不详细说明了。

这种组合的输出结果如下：

5 4 3

2

1

3 2

1

2 1

4 3 2

1

2 1

3 2 1

自己也写了一下，使用一个缓冲区记录选取的组合数，来输出全部的组合序列：

算法如下：

void comb( int n, int m ,int buff[], int& count )

{

if( m == 0 )

{// 递归退出条件,打印回车

for( int i=0;i<count;++i)

printf("%d ", buff[i] );

printf("\n");

return;

}

for( int i=0; i<= n - m; ++i )

{

buff[count++] = n-i;

comb( n-i-1, m-1,buff,count );

--count;

}

}

输出的结果如下：

5 4 3

5 4 2

5 4 1

5 3 2

5 3 1

5 2 1

4 3 2

4 3 1

4 2 1

3 2 1