lemene

從集合中枚舉子集有許多種情況。這里集合是指廣義的，它可能包含相同的元素。先討論不含相同元素的集合，枚舉問題規(guī)定如下：從N個(gè)元素的集合中，取出R個(gè)的元素子集。根據(jù)子集的不同性質(zhì)可分為：

一，子集是否可以重復(fù)包含某元素

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

上面兩種情況自由組合可分為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種。

下面討集合包含相同元素，這里的相同元素視為完全等同，可以替換。這樣集合含有兩個(gè)信息，一是含有N各不同的元素，二是每種元素有多少個(gè)。如果每種元素的個(gè)數(shù)為1，就是上面討論的情況。這里增加了新的討論條件，子集重復(fù)包含某元素的個(gè)數(shù)是否可以超過集合中該元素的個(gè)數(shù)。上一種情況，重復(fù)包含就意味超過。而在這里，就要分情況處理。

表二

例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發(fā)現(xiàn)情況1，2，3，4結(jié)果一樣，其實(shí)在可以超過的條件下，集合某個(gè)元素的個(gè)數(shù)是不起限制作用，結(jié)果也就一樣。所以可合并這兩種情況。從分析中知道，枚舉這樣的集合需要知道兩類信息。N種不同的元素和每種元素的個(gè)數(shù)。N種不同的元素可以映射到0至（N-1）N整數(shù)上。問題就變成了枚舉N個(gè)整數(shù)。枚舉出來的數(shù)字可以映射到原先的元素。N和表示每種元素個(gè)數(shù)的數(shù)組就是需要的信息。

// 構(gòu)造函數(shù)
// 輸入?yún)?shù)：max表示集合元素的個(gè)數(shù)
// 輸入?yún)①悾篹le_num 表示第i個(gè)元素的個(gè)數(shù)
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個(gè)元素就是取R個(gè)數(shù)，每個(gè)數(shù)的取值0至（N-1）。這樣每個(gè)子集對(duì)應(yīng)一個(gè)R位N進(jìn)制的數(shù)。于是枚舉數(shù)從0到N^R_-1，就枚舉出每種可能的子集，然后判斷子集是否滿足條件。

// 得到下一個(gè)子集合
// 輸出參數(shù)：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：每個(gè)枚舉數(shù)都滿足要求。

// 子集合是否滿足可重復(fù)，有序條件
// 輸出參數(shù)：subset得到的子集合
// 返回值：1表示符合，0表示不符合
int CSetIter::IsMultOrdered(std::vector<int>& subset)
{
    return 1;
}

情況2：枚舉數(shù)高位的數(shù)字不大于低位的數(shù)字。

// 子集合是否滿足可重復(fù)，無序條件
// 輸出參數(shù)：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：枚舉數(shù)的各位數(shù)字不能相同。

// 子集合是否滿足不重復(fù)，有序條件
// 輸出參數(shù)：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：枚舉數(shù)高位的數(shù)字小于低位的數(shù)字。

// 子集合是否滿足不重復(fù)，無序條件
// 輸出參數(shù)：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：數(shù)字在枚舉數(shù)出現(xiàn)的次數(shù)不能超過該數(shù)字對(duì)應(yīng)元素的個(gè)數(shù)。

// 子集元素重復(fù),有序，不能超出集合
// 輸出參數(shù)：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。

// 子集元素重復(fù),無序，不能超出集合
// 輸出參數(shù)：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;
}

其他實(shí)現(xiàn)見代碼。

代碼編譯方式：

g++ SetIter.cpp -D_SETITER_TEST_ 編譯，運(yùn)行。可看到例1的結(jié)果，

g++ SetIter.cpp -D_SETITERAGENT_TEST_ 編譯，運(yùn)行，就可以看到例2的結(jié)果。