包含重复元素的全组合解决办法

包含重复元素的全组合
题目要求：一个数组中，包含n个元素，可能包含重复元素，这n个元素按照非递减顺序排列，求从这n个元素中取出m个元素的所有组合？
 为了方便起见，定义程序接口如下：

 int allCombo(int data[], int n, int m);

 运行这个函数allCombo时，应该能够打印出所有组合，并返回组合的个数
 
 例如：
 data[]={2,2,3,3,5}
 运行 allCombo(data,5,3) 应该能够显示下列组合。
 {2,2,3}
 {2,2,5}
 {2,3,3}
 {2,3,5}
 {3,3,5}


[解决办法]
这不像是楼主的问题，什么意思？又摆擂台？

去除重复值之后得到新数组a[]，假设a数组大小为k，不重复的元素值共有k个
每个a[i]值在原data[]数组中出现的次数用c[i]来记录

用dp[i,j]来表示从a[]数组前i种元素中取j个的组合方案数，这里1<=i<=k
边界条件：
dp[i,0]=1，1<=i<=k
dp[i,j]=0，j<0
dp[1,j]=1，1<=j<=c[1]
dp[1,j]=0，j>c[1]
状态转移：
dp[i,j]=∑dp[i-1,j-t]（这里0<=t<=c[i]）
最后dp[k,m]就是不重复的组合方案总数

输出所有组合情况的时候同样根据这个二维数组来，含义很明显的。
[解决办法]
如果是输出所有组合，同样可以用略为修改后的“序列法”（或者叫“字典序”法？忘记名字了）
2 2 3 3 5
----------
1 1 1 0 0
1 1 0 0 1
1 0 1 1 0
1 0 1 0 1
0 0 1 1 1 
对应你说的那5种情况
[解决办法]
求约数不应该用字典序,两回事!

以{2,2,3,3,5}为例,2个2\2个3\1个5

{1,2,4}
{1,3,9}
{1,5}

从每个集合里面选1个!

所以总共(2+1)(2+1)(1+1)=18个!

[解决办法]
回到这个问题本身。写了段代码，还有很大优化余地：

C/C++ code

#include<iostream>using namespace std;bool nextcomb(int *data, int *p, int n, int m){    int last = n-1;    int i, j, k, temp;    i = last;    while(i>0 && !(p[i-1]==1 && p[i]==0))        i--;    if(i == 0)        return false;    p[i]=1;    p[i-1]=0;         if( data[i] == data[i-1] )    {        return nextcomb(data,p,n,m);    }    else    {        for(j=last, k=i+1; k<j; k++,j--)        {              temp = p[k];            p[k] = p[j];            p[j] = temp;        }        for(int h=0; h<n; h++)        {            if(p[h]==1) cout<<data[h]<<"  ";        }        cout<<endl;        return true;    }}int allCombo(int data[], int n, int m){    int i;              int *p = new int[n];      for(i=0; i<m; i++)    {        p[i]=1;        cout<<data[i]<<"  ";    }    cout<<endl;    for(i=m; i<n; i++)        p[i]=0;    int count = 1;            while( nextcomb(data,p,n,m) )    {        count++;    }    delete p;    return count;}int main(){    int data[]={2,2,3,3,5};    cout<<"共有"<<allCombo(data, 5, 3)<<"种";    return 0;}
[解决办法]
求因数不用这么复杂，是一个混合进制的问题。
以{2,2,3,3,5}为例,混合进制是{2,2,1}，即：个位满1进1；十位满2进1；百位满2进1。
而n个元素中取出m个元素的多重组合，也是一个带约束的混合进制问题。
[解决办法]
探讨

呵呵，{2,2,3,3,5}的混合进制应该是{3,3,2}。 
因此，一个循环搞定.      

[解决办法]
呵呵，我来扩展一下吧。

对求n的所有因子的问题，如上所说，我们可以转化为一个混合进制的问题。
现在，我们来考虑实现技巧。

显然，如果直接模仿10进制的进位操作，那么，可能在得到下一个数的时候，需要多次进位。
比如，混合进制{3,3,2}。 那么，在这个混合进制下，对121来说，下一个数是200。可以看到，在得到200的过程中，进位发生了两次，同时也要比较三次。

如何使从上一个数到下一个数的操作尽量少？我们考虑Gray Code.
一般意义下的Gray Code是二进制的，它满足：上个码与下一个码的组成中仅仅只有一位发生变化。

对混合进制而言，是否也有这样的"Gray code"？如果有，如何构造？

如果解决了上面这两个问题，我们就有一个效率很完美的实现了。
[解决办法]
减少进位可以将较大的进位排在后面,比如{5,4,3,3,2}排成{2,3,3,4,5}

进位次数大概是2*3*3*4*1 + 2*3*3*2 + 2*3*3 + 2*4

整体复杂度应当不会翻倍，反正我也不是那么追求效率。 
 

探讨

呵呵，我来扩展一下吧。 

对求n的所有因子的问题，如上所说，我们可以转化为一个混合进制的问题。 
现在，我们来考虑实现技巧。 

显然，如果直接模仿10进制的进位操作，那么，可能在得到下一个数的时候，需要多次进位。 
比如，混合进制{3,3,2}。 那么，在这个混合进制下，对121来说，下一个数是200。可以看到，在得到200的过程中，进位发生了两次，同时也要比较三次。 

如何使从上一个数到下一个数的操作尽量少？我们…

[解决办法]
简单的说就是有N个数，每个数的数目不妨设为Y[i]。
计算sum(X[i]) = C(C为组合的大小)，在限制X[i] <= Y[i]的解的个数

解法有很多，有DP,母函数法等。


[解决办法]
//好歹也给出了个程序，给点分吧
//复杂度很低

#include <stdio.h>
#include <string.h>

#define MAXN 10000
int count[MAXN];
int countlen;

int rollA[MAXN+1];
int rollB[MAXN+1];

void initcount(int data[],int n)
{
   int i,j,c;
   c = 1;
   for(i = 1,j = 0;i < n;i++)
   {
       if(data[i] != data[i-1])
       {
           count[j] = c;
           j++;
           c = 1;
       }
       else
       {
           c++;
       }
   }
   count[j] = c;
   countlen = j+1;
}

void getCombo(int ra[],int rb[],int m,int dep)
{
   int i,j;
   rb[0] = 1;
   for(i = 1;i <= m;i++)
   {
       rb[i] = 0;
       for(j = 0;j <= count[dep] && i-j >= 0;j++)
           rb[i] += ra[i-j];
   }
}

int allCombo(int data[], int n, int m)
{
   int i;
   initcount(data,n);
   rollA[0] = 1;
   for(i = 0;i < countlen;i++)
   {
       if(i%2 == 1)
       {
           getCombo(rollB,rollA,m,i);
       }
       else
       {
           getCombo(rollA,rollB,m,i);
       }
   }
   if(i%2) return rollB[m];
   else return rollA[m];
}  

int main()
{
   int data[]={2,2,3,3,5};
   printf("%d\n",allCombo(data, 5, 3));
   return 0;
}


[解决办法]
其实就是某楼说的DP,同时减少了点空间负责度