我正在尝试编写代码，通过一个条件从集合中生成所有子集，例如 如果我有 threshold =2，并且设置了三个:

1, 2, 3, 4, 5
1,3,5
1,3,4

然后程序会输出:

第一次迭代时的生成集:

1 = number of frequency = 3
2 = number of frequency = 1
3 = number of frequency = 3
4 = number of frequency = 2
5= number of frequency = 2

由于数字 2 <>

第二次迭代时的生成集:

1,3 = number of frequency = 3
1,4 = number of frequency = 2
1,5 = number of frequency = 2
3,4 = number of frequency = 2
3,5= number of frequency = 2
4,5= number of frequency = 1

因为数字 (4,5) <>

第三次迭代时的生成集

1,3,4= number of frequency = 2
1,3,5= number of frequency = 2

第四次迭代时的生成集

没有更多的超集，因为 (4,5) < 阈值我们无法生成="" (1,3,4,5)="">

我写了这个程序，我已经生成了所有的子集，但是有两件事失败了:

• 我无法在 map 中搜索 std::map <int,std::pair<list<int>, int>> CandList统计相似集(频数)
• 我不知道如何应用条件

感谢任何帮助。

这是我的代码:

int threshold = 2;
std::vector<std::list<int>> data;
std::map<int, int> FISupp;
typedef std::pair<list<int>, int> combo;
std::map <int,combo> CandList;
std::list<int> FrqList;



/*
input:Threshold =2, and data=
1 2 3 4 5
1 3 4 5
1 2 3 5
1 3

at first scan after PassOne function:
FISupp(1,4)
FISupp(2,2)
FISupp(3,4)
FISupp(4,4)
FISupp(5,3)

at k scan after Passk function:
---
*/
int Lsize = 2; // Level size

void ScanData()
{
    ifstream in;
    in.open("mydata.txt");
    /* mydata.txt
    1 2 3 4 5
    1 3 4 5
    1 2 3 5
    1 3
    */
    std::string line;
    int i = 0;

    while (std::getline(in, line))
    {
        std::stringstream Sline1(line);
        std::stringstream ss(line);
        std::list<int> inner;
        int info;

        while (ss >> info)
            inner.push_back(info);

        data.push_back(inner);
    }
}


/* first pass to generate first Candidates items */
void PassOne()
{
    for (unsigned i = 0; i < data.size(); ++i)
    {
        std::list<int>::iterator li;

        for (li = data[i].begin(); li != data[i].end(); ++li)
            FISupp[*li] += 1;
    }


    /*update the FFISupp by erasing all first Candidates items  with support < Threshold*/

    std::map<int, int> ::iterator current = FISupp.begin();

    std::list<int> ls; /* save Candidates itemes with support < Threshold*/
    while (current != FISupp.end())
    {
        if (current->second < threshold)
        {
            ls.push_back(current->first);
            current = FISupp.erase(current);
        }
        else
            ++current;
    }


    /*update the the orginal data by erasing all first Candidates items  with support < Threshold*/
    for (unsigned i = 0; i < data.size(); ++i)
    {
        std::list<int>::iterator li;
        std::list<int>::iterator item = ls.begin();

        while (item != ls.end())
        {
            for (li = data[i].begin(); li != data[i].end(); ++li)
            {
                if (*li == *item)
                {
                    li = data[i].erase(li);
                    break;
                }
            }
            ++item;
        }

    }


}


void FrequentItem(list<int> l,   int indx)
{
    int a = 0;
    for (list<int>::iterator it = l.begin(); it != l.end(); ++it)
    {
        //std::list <int> &m2 = CandList[indx].first;

        //auto itr = m2.find(*it);

        //auto itr = std::find(CandList.begin(), CandList.end(), *it);

        auto itr = CandList.find(*it);
        if (itr != CandList.end())
        {
            a += CandList[indx].second;
            CandList[indx].first.push_back(*it);
            CandList[indx].second = a;
        }

    }

}

int ind = 0;
void Passk(int j, std::list<int>::iterator Itm , int q = 0)
{

    if (Lsize == q)
    {
        FrequentItem(FrqList, ind);
        ++ind;
        return;
    }

    else
    {

        for (std::list<int>::iterator Itm2 = Itm; Itm2 != data[j].end(); ++Itm2)
        {
                FrqList.push_back(*Itm2);
                Passk(j,  ++Itm2, q + 1);
                FrqList.pop_back();
                --Itm2;

        }

    }


}



void main(int argc, char *argv[])
{
    int temp = 0;
    int j = -1;

    ScanData();
    PassOne();

    while (Lsize <= data.size()) // How to stop the loop when there is no more candidate >= threshold???
    {
        for (unsigned i = 0; i < data.size(); ++i)
        {
            std::list<int>::iterator items = data[i].begin();
            Passk(++j, items);  
        }

        j = -1;
        ++ Lsize;

    }

    data.clear();
    system("PAUSE");
    return;
}

最佳答案

好的，我会尽力解答。但首先是假设:

• 您正在使用有序 集，即元素严格升序。
• 您考虑“正常”集，即没有可能出现重复元素的多集。
• 这两个假设可能很容易放宽，但我将以此为基础。

对于这种情况，通过位 vector 对集合进行编码可能更自然(例如使用 std::vector<bool> 或 boost::dynamic_bitset<> )。在这样的位 vector 中，如果 i第-个元素被设置，表示第i个数存在于集合中。

比如你的三个集合是这样表示的

1 1 1 1 1
1 0 1 0 1
1 0 1 1 0

迭代 1:在您的第一次迭代中，您只需对元素求和，这在此表示中相当容易。一个获得

    1 1 1 1 1
    1 0 1 0 1
    1 0 1 1 0
   -----------
    3 1 3 2 2

接下来丢弃低于阈值的所有元素，这相当于将第二行设置为零:

    1 0 1 1 1
    1 0 1 0 1
    1 0 1 1 0

Iteration K:在这里，您计算所有 K 子集的出现次数，如果它们的数量小于阈值，则丢弃它们。也就是说，正式地，您生成 K-stencils

{ 1 1 0 0 0, 1 0 1 0 0, ... , 0 0 0 1 1}   (for K=2)
{ 1 1 1 0 0, 1 1 0 1 0, ... , 0 0 1 1 1}   (for K=3)

等等。对于这些中的每一个 K -stencils，你计算出现次数并最终丢弃(注意 K 也可能是一个)。所以，你有三个任务，即

1. 生成:通过初始位 vector {1 ... 1 0 ... 0}的排列获得, 其中K元素向左排序。

2. 计数:遍历集合的 vector ，并使用按位 and检查当前 vector 是否包含模板。例如:1 0 1 1 1 & 0 0 0 1 1 == 0 0 0 1 1 ？。

3. 丢弃:通过按位应用反转模板 and (反转通过 flip() 完成)。这将删除相关的子集。最后丢弃任何小于迭代次数的子集(例如，在第 3 次迭代中，移除大小为 2 的子集)。

这是一个主要使用 boost::dynamic_bitset<> 的实现，但是 std::vector<bool>对于排列(那是因为我不想自己编写排列，但这当然可以改进)。请注意，没有 map 或其他更复杂的存储方案:

#include<vector>
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<boost/dynamic_bitset.hpp>

//only for nice output of a bitset
std::string screenOutput(const boost::dynamic_bitset<>& bits)
{
    int n=bits.size();
    std::string ret;
    for(int i=n-1;i>=0;--i)
    {
        if(bits[i])
        {
           std::stringstream out;
           out<<i+1<<" ";
           ret=out.str()+ret;
        }
    }
    return "{"+ret+"}";
}

//function implementing the actual logic
void removeSubsets(std::vector<boost::dynamic_bitset<> > &currentSet, size_t K, size_t thresh)
{
    size_t n=currentSet.front().size();

    //create initial stencil {1 ... 1 0 ... 0}
    std::vector<bool> stencil(n);
    for(size_t i=0;i<K;++i)
        stencil[i]=true;

    //apply permutations to initial stencil
    do
    {
         //generate dynamic_bitset from permuted vector<bool>
         boost::dynamic_bitset<> temp(n);
         for(size_t i=0;i<n;++i)
              temp[i]=stencil[i];

         //count the occurence of the stencil
         size_t count=0;
         for(size_t j=0;j<currentSet.size();++j)
         {
              if((currentSet[j] & temp) == temp)
                 ++count;
         }

         //remove if at least one and less than thresh is found
         if(count<thresh && count>0)
         {
              boost::dynamic_bitset<> tempFlip=temp;
              tempFlip.flip();
              for(size_t j=0;j<currentSet.size();++j)
              {
                    //remove stencil from all bitset which contain it
                    if((currentSet[j] & temp) == temp)
                      currentSet[j]= (currentSet[j] & tempFlip);
              }
         }
    }
    while(std::prev_permutation(stencil.begin(),stencil.end()));

    //further remove all supersets which contain less than K elements
    for(size_t j=0;j<currentSet.size();++j)
         if(currentSet[j].count()<K)
         {
               currentSet[j]=boost::dynamic_bitset<>(n,0);
         }
}

代码可以这样使用:

int main()
{
    //initialize set of three bit-vectors (all elements to true)
    std::vector<boost::dynamic_bitset<> > yourSet(3, boost::dynamic_bitset<>(5, (1<<5)-1) );

    //set corresponding elements to false
    yourSet[1][1]=false;
    yourSet[1][3]=false;
    yourSet[2][1]=false;
    yourSet[2][4]=false;

    std::cout<<"Original sets"<<std::endl;
    for(size_t i=0;i<3;++i)
        std::cout<<screenOutput(yourSet[i])<<std::endl;
    std::cout<<std::endl;

    removeSubsets(yourSet, 1, 2);
    std::cout<<"After iteration 1:"<<std::endl;
    for(size_t i=0;i<3;++i)
        std::cout<<screenOutput(yourSet[i])<<std::endl;
    std::cout<<std::endl;

    removeSubsets(yourSet, 2, 2);
    std::cout<<"After iteration 2:"<<std::endl;
    for(size_t i=0;i<3;++i)
        std::cout<<screenOutput(yourSet[i])<<std::endl;
    std::cout<<std::endl;

    removeSubsets(yourSet, 3, 2);
    std::cout<<"After iteration 3:"<<std::endl;
    for(size_t i=0;i<3;++i)
        std::cout<<screenOutput(yourSet[i])<<std::endl;
    std::cout<<std::endl;
}

输出:

Original set:
{1 2 3 4 5}
{1 3 5}
{1 3 4}

After iteration 1:
{1 3 4 5}
{1 3 5}
{1 3 4}

After iteration 2:
{}
{1 3 5}
{1 3 4}

After iteration 3:
{}
{}
{}

伙计，我显然时间太多了。

编辑:更正代码。您仍然必须检查它是否真的带来了您想要的东西。

关于C++ : generate all subsets from set with one condition，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23880118/