编程怎么实现排列组合程序

码拜

9年 ago

现在碰到一个问题,涉及到排列组合的乘法:
假设有n类物品, 每类物品的数量不定,现在要从每类物品中取一个,然后对其进行排列组合,把每种组合列出来.
例如:
n=4
a类：a1 a2
b类：b1 b2
c类：c1
d类：d1
组合：a1 b1 c1 d1, a1 b2 c1 d1, a2, b1 c1 d1, a2 b2 c1 d1
编程怎么实现啊？n是不定的每类数量也是不定的

设有n类物品, 每类物品的数量为m[i]

类  物品名称                                      物品序号
0   a[0][0]   a[0][1]   ... a[0][m[0]-1]     | 0 .. m[0]-1  |
1   a[1][0]   a[1][1]   ... a[1][m[1]-1]     | 0 .. m[1]-1  |
2   a[2][0]   a[2][1]   ... a[2][m[2]-1]     | 0 .. m[2]-1  |
.   ........................................ | ...........  |
.   ........................................ | ...........  |
.   ........................................ | ...........  |
n-1 a[n-1][0] a[n-1][1] ... a[n-1][m[n-1]-1] | 0 .. m[n-1]-1|

设(x[0],x[1],x[2],…,x[n-1])表示选择第0类中的第x[0]个,第1类中的第x[1]个,第2类中的第x[2]个,…,第n-1类中的第x[n-1]个
例如:(0,0,0,…,0)表示都选第0个,(m[0]-1,m[1]-1,…,m[n-1]-1)表示都选最后一个,
将(x[0],x[1],x[2],…,x[n-1])看成是n位m[i]进制的数字,第0位进制为m[0],第1位进制为m[1],…,第n-1位进制为m[n-1],
那么遍历(0,0,0,…,0)到(m[0]-1,m[1]-1,…,m[n-1]-1)就可以遍历完全部的排列情况
遍历方法如下

#include<iostream>
#include<vector>
#include<iterator>
using namespace std;
int main()
{
    unsigned int n;
    cin>>n;
    vector<unsigned int> m(n);
    unsigned int M=1;
    for(unsigned int i=0;i<n;++i)
    {
        cin>>m[i];
        M*=m[i];
    }
    for(unsigned int i=0;i<M;++i)
    {
        unsigned int t=i;
        vector<unsigned int> x(n);
        for(unsigned int j=0;j<n;++j)
        {
            x[j]=t%m[j];
            t/=m[j];
        }
        copy(x.begin(),x.end(),ostream_iterator<unsigned int>(cout," "));
        cout<<endl;
    }
    return 0;
}