//从M个数中取出N个数组合
#include <iostream>
using namespace std;
void jisuan(int a[],int m,int n,int k,int temp);
int num(int m,int n);
int jiecheng(int a);
void main()
{
int m,n;
cout<<"请输入M和N："<<endl;
cin>>m>>n;
cout<<"一共 "<<num(m,n)<<" 种组合"<<endl;
int a[100];
jisuan(a,m,n,-1,-1);
}
void jisuan(int a[],int m,int n,int k,int temp)
{
temp++;
if(temp<n)
for(int i=k+1;i<m;i++)
{
a[temp]=i+1; //赋值
jisuan(a,m,n,i,temp); //递归调用
}
else
{
for(int j=0;j<n;j++)
{
cout<<"\t"<<a[j]; //输出
}
cout<<endl;
}
}
//计算个数
int num(int m,int n)
{
int sum;
sum=jiecheng(m)/(jiecheng(n)*jiecheng(m-n));
return sum;
}
//求阶乘
int jiecheng(int a)
{
int h=1;
for(int i=1;i<=a;i++)
h=h*i;
return h;
}

very nice algorithm for combinations.

1. There are "standard" combination algorithms which uses iteration out there. You may search codeproject.com for "next_combination".
2. Your "num(m, n)" of calculating m choose n could be improved --- num(17, 2) won't work, numOfComb(17, 2) does work. Overflow, overflow, overflow!


int numOfComb(int m, int n)
{
int r=1;
int i;

for(i=1; i<=n; ++i)
{
r *= (m-i+1);
r /= i;
}

return r;
}

版主说的没错,果然是高手,我收益非浅,谢谢拉

不过以后请用中文!

现改正如下
#include <iostream>
using namespace std;
void jisuan(int a[],int m,int n,int k,int temp);
int numOfComb(int m, int n);
void main()
{
int m,n;
cout<<"请输入M和N："<<endl;
cin>>m>>n;
cout<<"一共 "<<numOfComb(m,n)<<" 种组合"<<endl;
int a[100];
jisuan(a,m,n,-1,-1);
}
void jisuan(int a[],int m,int n,int k,int temp)
{
temp++;
if(temp<n)
for(int i=k+1;i<m;i++)
{
a[temp]=i+1; //赋值
jisuan(a,m,n,i,temp); //递归调用
}
else
{
for(int j=0;j<n;j++)
{
cout<<"\t"<<a[j]; //输出
}
cout<<endl;
}
}
//计算个数
int numOfComb(int m, int n)
{
int r=1;
int i;

for(i=1; i<=n; ++i)
{
r *= (m-i+1);
r /= i;
}

return r;
}

[QUOTE]不过以后请用中文![/QUOTE]

[QUOTE]I am working on a system which has no Chinese input. Please don't blame me for typing English.[/QUOTE]

他用不了的。

英文不错的，LS你六级过了没？

没查，证在寝室的！

估计没有！嘿嘿！

我下学期报，好贵哦六级，我们学校最贵

/*---------------------------------------------------------------------------
File name: Perm-noLexic.cpp
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 8/24/2007 01:53:37
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:
===========================================================================

Here is what I wrote a long long time ago. I used one buffer, but the output
is NOT in lexicographic order.

If you want to the lexicographic order, you can use an extra buffer.

冰的热度's algorithm is one of the best if the numbers are 1..n; if the numbers
are not 1..n, say {1, 3, 4, 6, 9}, you have to modify his algorithm.

C++'s next_permutation() and prev_permutation() work for containers and thus,
in general, you may want to use these two "library" functions instead.

Sample output:
---------------------------------------------------------------------------
1: 1 3
2: 1 4
3: 1 6
4: 1 9
5: 3 4
6: 3 6
7: 3 9
8: 3 1
9: 4 6
10: 4 9
11: 4 1
12: 4 3
13: 6 9
14: 6 1
15: 6 3
16: 6 4
17: 9 1
18: 9 3
19: 9 4
20: 9 6
Press any key to continue . . .
*/

#include <iostream>
using namespace std;

// Permutation of n numbers choose k numbers
// k=1..n.
int a[]={1, 3, 4, 6, 9};
int n=5;
int k=2;

void permute();
void do_permute(int m);
void rotate(int m);

int main()
{
permute();

return 0;
}

void permute()
{
do_permute(n);
}

void do_permute(int m)
{
static int count=0;
if(m==n-k)
{
++count;
cout<<count<<": ";
for(int i=0; i<k; ++i)
cout<<a[i]<<" ";
cout<<endl;

return;
}

for(int i=0; i<m; ++i)
{
do_permute(m-1);
rotate(m);
}
}

void rotate(int m)
{
int t=a[n-m];

for(int i=n-m; i<n; ++i)
a[i]=a[i+1];

a[n-1]=t;
}

我看了那个 求组合的泛型算法 ，果然很强大。

用迭代到看懂了，递归那个还是不明白。

有空我整理出来，大家一起研究。嘿嘿~

that is good.

The one with iteration is hard to understand.

I encourage you to write an article about Permutation and Combination and sticky it so that every beginner can benefit from your work.