lemene

从集合中枚举子集有许多种情况。这里集合是指广义的，它可能包含相同的元素。先讨论不含相同元素的集合，枚举问题规定如下：从N个元素的集合中，取出R个的元素子集。根据子集的不同性质可分为：

一，子集是否可以重复包含某元素

二，子集的元素是否有序。

上面两种情况自由组合可分为4种情形，见下表：

表一

例1：按照这4种情况，枚举集合{a，b，c}，其中R=2。

情况1：有{a，a}，{a，b}，{a，c}，{b，a}，{b，b}，{b，c}，{c，a}，{c，b}，{c，c}9种。

情况2：有{a，a}，{b，b}，{c，c}，{a，b}，{a，c}，{b，a}6种。

情况3：有{a，b}，{a，c}，{b，a}，{b，c}，{c，a}，{c，b}6种。

情况4：有{a，b}，{a，c}，{b，a}3种。

下面讨集合包含相同元素，这里的相同元素视为完全等同，可以替换。这样集合含有两个信息，一是含有N各不同的元素，二是每种元素有多少个。如果每种元素的个数为1，就是上面讨论的情况。这里增加了新的讨论条件，子集重复包含某元素的个数是否可以超过集合中该元素的个数。上一种情况，重复包含就意味超过。而在这里，就要分情况处理。

表二

例2：按照这6种情况，枚举集合{a，a，b，c}，其中R=2。

情况1：有{a，a}，{a，b}，{a，c}，{b，a}，{b，b}，{b，c}，{c，a}，{c，b}，{c，c}9种。

情况2：有{a，a}，{b，b}，{c，c}，{a，b}，{a，c}，{b，a}6种。

情况3：有{a，b}，{a，c}，{b，a}，{b，c}，{c，a}，{c，b}6种。

情况4：有{a，b}，{a，c}，{b，a}3种。

情况5：有{a，a}，{a，b}，{a，c}，{b，a}，{b，c}，{c，a}，{c，b}7种。

情况6：有{a，a}，{a，b}，{a，c}，{b，a}4种。

比较例1和例2发现情况1，2，3，4结果一样，其实在可以超过的条件下，集合某个元素的个数是不起限制作用，结果也就一样。所以可合并这两种情况。从分析中知道，枚举这样的集合需要知道两类信息。N种不同的元素和每种元素的个数。N种不同的元素可以映射到0至（N-1）N整数上。问题就变成了枚举N个整数。枚举出来的数字可以映射到原先的元素。N和表示每种元素个数的数组就是需要的信息。

// 构造函数
// 输入参数：max表示集合元素的个数
// 输入参赛：ele_num 表示第i个元素的个数
CSetIter::CSetIter(unsigned long max, const std::vector<int>& ele_num) :
    m_ele_num(ele_num)
{
    assert(max == ele_num.size());
    m_max = max;
}

枚举R个元素就是取R个数，每个数的取值0至（N-1）。这样每个子集对应一个R位N进制的数。于是枚举数从0到N^R_-1，就枚举出每种可能的子集，然后判断子集是否满足条件。

// 得到下一个子集合
// 输出参数：subset得到的子集合
// 返回值：1表示成功取得，0表示没有取得，枚举完毕
int CSetIter::GetNextSubset(std::vector<int>& subset)
{

    assert(subset.size() == m_size);
    while (m_iter_num < m_iter_max)
    {
        // 判断是否符合条件
        if ((this->*m_pfnIsSubsetOk)(m_iter_v))
        {
            subset = m_iter_v;
            IncIterNum();
            return 1;
        }
        IncIterNum();
    }
    return 0;
}

下面分别讨论这六种情况如何判断。

情况1：每个枚举数都满足要求。

// 子集合是否满足可重复，有序条件
// 输出参数：subset得到的子集合
// 返回值：1表示符合，0表示不符合
int CSetIter::IsMultOrdered(std::vector<int>& subset)
{
    return 1;
}

情况2：枚举数高位的数字不大于低位的数字。

// 子集合是否满足可重复，无序条件
// 输出参数：subset得到的子集合
// 返回值：1表示符合，0表示不符合
int CSetIter::IsMultDisorder(std::vector<int>& subset)
{
    for (int i=0; i<m_size-1; i++)
    {
        if (subset[i] > subset[i+1])
            return 0;
    }
    return 1;
}

情况3：枚举数的各位数字不能相同。

// 子集合是否满足不重复，有序条件
// 输出参数：subset得到的子集合
// 返回值：1表示符合，0表示不符合
int CSetIter::IsSingleOrdered(std::vector<int>& subset)
{
    for (int i=0; i<m_size-1; i++)
    {
        for (int j=i+1; j<m_size; j++)
        {
            if (subset[i] == subset[j])
                return 0;
        }
    }
    return 1;
}

情况4：枚举数高位的数字小于低位的数字。

// 子集合是否满足不重复，无序条件
// 输出参数：subset得到的子集合
// 返回值：1表示符合，0表示不符
int CSetIter::IsSingleDisorder(std::vector<int>& subset)
{
    for (int i=0; i<m_size-1; i++)
    {
        if (subset[i] >= subset[i+1])
            return 0;
    }
    return 1;
}

情况5：数字在枚举数出现的次数不能超过该数字对应元素的个数。

// 子集元素重复,有序，不能超出集合
// 输出参数：subset得到的子集合
// 返回值：1表示符合，0表示不符
int CSetIter::IsMultOrderedIn(std::vector<int>& subset)
{
    std::vector<int> tmp(m_ele_num.size(), 0);
    for (int i=0; i<m_size; i++)
    {
        tmp[subset[i]]++;
        if (tmp[subset[i]] > m_ele_num[subset[i]])
            return 0;
    }
    return 1;
}

情况6：情况5加上情况2。

// 子集元素重复,无序，不能超出集合
// 输出参数：subset得到的子集合
// 返回值：1表示符合，0表示不符
int CSetIter::IsMultDisorderIn(std::vector<int>& subset)
{
    std::vector<int> tmp(m_ele_num.size(), 0);
    for (int i=0; i<m_size-1; i++)
    {
        if (subset[i] > subset[i+1])
            return 0;
    }
    for (int i=0; i<m_size; i++)
    {
        tmp[subset[i]]++;
        if (tmp[subset[i]] > m_ele_num[subset[i]])
            return 0;
    }
    return 1;
}

其他实现见代码。

代码编译方式：

g++ SetIter.cpp -D_SETITER_TEST_ 编译，运行。可看到例1的结果，

g++ SetIter.cpp -D_SETITERAGENT_TEST_ 编译，运行，就可以看到例2的结果。