请教高手从m个数中任取n个数的组合算法（可以重复）
我想问问有m个数，如果任意输入n，可以实现m中取n的组合算法，数字可以允许重复。比如有3个数1，2，3，n=3，则一共有111，112，113，221，222，223，331，332，333，123种取法（123，321，231中确只能有1个）。即需要满足公式，C(m,n)=(m+n-1)!/n!(m-1)!，有哪位高手能帮帮忙？想了很久都不得其解，谢谢先! 搜索更多相关的解决方案:
算法
----------------解决方案--------------------------------------------------------
有没有哪位高手大虾知道啊，想了两个星期了，编的程序只能取出无重复的。谢谢先！！！
----------------解决方案--------------------------------------------------------
别说你 我都想了3天了 想不出
----------------解决方案--------------------------------------------------------
我现在编的程序可以取出不同数的类似1234，1356和完全重复的1111，2222，最难的就是如何实现有部分重复的比如1122，1113，1145之类的。
----------------解决方案--------------------------------------------------------
不难，直接DFS
不过楼主，我想看看你写的代码
[color=white]
----------------解决方案--------------------------------------------------------
重复的取数字，c(m,n)不是m的n次方么？
楼主 确定 你给的 算法没错？
----------------解决方案--------------------------------------------------------
先谢谢楼上诸位的先！
重复取数字是指每一种取法中数字可以有重复，比如说112，111可以，不过112和121，211却只能出现一次。
我当时只想要结果，不在乎算法，所以我自己编时用的是最笨的方法，一个一个实现。
先是编数字完全没有一样的，象123，234这样的，我用的算法
int a[2000];
int a[1]=1;km=1;
while(n-a[1]>=m)
{while(km<m)
{km++;
a[km]=a[km-1]+1;
}
for(;a[km]<=n;a[km]++)
{kinds++;
for(i=1;i<=m;i++)
printf("%5d",a[i]);
printf("\n");
}
km--;
while(n-a[km]<=m-km)km--;
}
for(i=n-m+1;i<=n;i++)
printf("%5d",i);
然后编数字完全一样的，这个很容易，把每一个数取n次就可以了，不过最难的就是数字部分有重复的。
另我不是太懂DSF, 是一种数据结构吗？我是学化学的，老板非要我找出20种氨基酸可以组合成哪些种蛋白质，所以还要各位多多指教！
----------------解决方案--------------------------------------------------------
/*****************************************************************
** HighlightCodeV3.0 software by yzfy(雨中飞燕) http://yzfy.org **
*****************************************************************/
#include <iostream>
using namespace std;
template<class T>
int DFS_FindNext(T arr[], int nMaxElm, int nDepth)
{
int n = nDepth-1;
for (++arr[n]; n>=0 && arr[n]>=nMaxElm; ++arr[--n]);
if (n<0) return 0;
for (int t = n+1; t<nDepth; ++t) arr[t] = arr[n];
return 1;
};
int main()
{
int n,m;
while(scanf("%d%d",&m,&n)==2)
{
int arr[20]={0}, outmap[20]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
do
{
for(int t=0; t<n; ++t)
{
printf(" %d", outmap[arr[t]]);
}
putchar('\n');
}while(DFS_FindNext(arr, m, n));
}
return 0;
}
** HighlightCodeV3.0 software by yzfy(雨中飞燕) http://yzfy.org **
*****************************************************************/
#include <iostream>
using namespace std;
template<class T>
int DFS_FindNext(T arr[], int nMaxElm, int nDepth)
{
int n = nDepth-1;
for (++arr[n]; n>=0 && arr[n]>=nMaxElm; ++arr[--n]);
if (n<0) return 0;
for (int t = n+1; t<nDepth; ++t) arr[t] = arr[n];
return 1;
};
int main()
{
int n,m;
while(scanf("%d%d",&m,&n)==2)
{
int arr[20]={0}, outmap[20]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
do
{
for(int t=0; t<n; ++t)
{
printf(" %d", outmap[arr[t]]);
}
putchar('\n');
}while(DFS_FindNext(arr, m, n));
}
return 0;
}
是DFS，我想说写这个的确很容易，还有，我只准备了m在15以内，如果你要更大的你就自己加上吧
[color=white]
[[it] 本帖最后由 泉此方 于 2008-6-11 12:58 编辑 [/it]]
----------------解决方案--------------------------------------------------------
/*****************************************************************
** HighlightCodeV3.0 software by yzfy(雨中飞燕) http://yzfy.org **
*****************************************************************/
template<class T>
int DFS_FindNext(T arr[], int nMaxElm, int nDepth)
{
int n = nDepth-1, c = nMaxElm-nDepth;
for (++arr[n]; n>=0 && arr[n]>c+n; ++arr[--n]);
if (n<0) return 0;
for (int t = n+1; t<nDepth; ++t) arr[t] = arr[t-1],++arr[t];
return 1;
};
int main()
{
int n,m;
while(scanf("%d%d",&m,&n)==2)
{
int arr[30], outmap[30];
{for(int t=0;t<m;++t)arr[t]=t,outmap[t]=t+1;}
do
{
for(int t=0; t<n; ++t)
{
printf(" %d", outmap[arr[t]]);
}
putchar('\n');
}while(DFS_FindNext(arr, m, n));
}
return 0;
}
** HighlightCodeV3.0 software by yzfy(雨中飞燕) http://yzfy.org **
*****************************************************************/
template<class T>
int DFS_FindNext(T arr[], int nMaxElm, int nDepth)
{
int n = nDepth-1, c = nMaxElm-nDepth;
for (++arr[n]; n>=0 && arr[n]>c+n; ++arr[--n]);
if (n<0) return 0;
for (int t = n+1; t<nDepth; ++t) arr[t] = arr[t-1],++arr[t];
return 1;
};
int main()
{
int n,m;
while(scanf("%d%d",&m,&n)==2)
{
int arr[30], outmap[30];
{for(int t=0;t<m;++t)arr[t]=t,outmap[t]=t+1;}
do
{
for(int t=0; t<n; ++t)
{
printf(" %d", outmap[arr[t]]);
}
putchar('\n');
}while(DFS_FindNext(arr, m, n));
}
return 0;
}
这是无重复的，前面的是可重复的
[color=white]
----------------解决方案--------------------------------------------------------
我最喜欢燕子的代码了。。。
----------------解决方案--------------------------------------------------------