n选择k条件的实现 [英] n choose k implementation with condition

问题描述

我使用了本主题中的程式码
http://stackoverflow.com/a/5097100/3617657

并且我编辑它一点工作 std :: vector< std :: vector< int>> std :: vector< int>

K在我的case有不同的值4），而是只有一个值

<$ p $

p> 1 2 3 4
1 2 4
1 3


$ b b

if k = 3，然后对于我的数据中的每一行， n choose k =

  123 
 124 
 134 
 234 
 
 124 
 
 13 
  

但我想要我的地图结果，其中值表示子集的频率：

 （123，1）
（124，2）
 ）
（234，1）
 
（13，1）
  

这是我的代码：

  std :: vector< std :: vector< int& >数据; 
 
 std :: map< int，set< int>> CandidateSet; 
 typedef std :: pair< set< int>，int>组合
 std :: map< int，combo> CandidateSup; 
 
 
 
 
 
 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 :: vector< int>内; 
 int info 
 
 while（ss>> info）
 inner.push_back（info）; 
 
 data.push_back（inner）; 
} 
} 
 
 
 
 int main（）
 {
 ScanData（）; 
 std :: size_t k = 0; 
 int j = 0; 
 int c = 0; 
 int supp = 1; 
 int Lsize = 1; 
 while（Lsize <= 4）
 {
 for（unsigned i = 0; i  {
 std :: vector< int> :: iterator items = data [i] .begin（）; 
 if（Lsize> data [i] .size（））
 k = data [i] .size（）; 
 else 
 k = Lsize; （std :: vector< int> :: iterator items = data [i] .begin（）; j  
 do 
 
 {
 CandidateSet [c] .insert（* items）; 
 ++ j; 
} 
 
 ++ c; 
 std :: cout<< \\\
; 
 j = 0; 
 
} 
 while（next_combination（data [i] .begin（），data [i] .begin（）+ k，data [i] .end（） 
 
 
 
 / ******************************* **************************************************** ******************************************* 
 //这里我的问题
 //检查（next_combination）是否已经存在于CandidateSet中，如果是，添加一个到现有的支持
 
 auto it = CandidateSet.begin（）; 
 set< int> A = it-> second; 
 set< int> B; 
 
 B = CandidateSet [* items]; //我不知道如何设置为next_combination 
 
 
 while（it！= CandidateSet.end（））
 {//如果找到
 if（！（A< B）&&！（B< A））
 {
 CandidateSup [* items] = std :: make_pair（A，++ supp） 
 break; 
} 
 else 
 {//如果尚未找到
 ++ it; 
 A = it-> second; 
} 
} // end while 
 
 //如果不存在，添加这个新集合support = 1 
 ++ c; 
 CandidateSup [c] = std :: make_pair（B，supp）; 
 / ********************************************* **************************************************** ******************************* / 
 
} 
 ++ Lsize; 
 
} 
 
 data.clear（）; 
 
 
 
 
 
系统（PAUSE）; 
 return 0; 
} 
  

此combination.h >

  template< typename Iterator> 
 inline bool next_combination（const Iterator first，Iterator k，const Iterator last）
 {
 / *学分：Thomas Draper * / 
 if（（first == last）|| （first == k）||（last == k））
 return false; 
迭代器itr1 =第一; 
迭代器itr2 = last; 
 ++ itr1; 
 if（last == itr1）
 return false; 
 itr1 = last; 
 --itr1; 
 itr1 = k; 
 --itr2; 
 while（first！= itr1）
 {
 if（*  -  itr1 <* itr2）
 {
迭代器j = k; 
 while（！（* itr1< * j））++ j; 
 std :: iter_swap（itr1，j）; 
 ++ itr1; 
 ++ j; 
 itr2 = k; 
 std :: rotate（itr1，j，last）; 
 while（last！= j）
 {
 ++ j; 
 ++ itr2; 
} 
 std :: rotate（k，itr2，last）; 
 return true; 
} 
} 
 std :: rotate（first，k，last）; 
 return false; 
} 
  

解决方案

https://ideone.com/5EPuGd ）

  std :: map< std :: set< int>，int>计数; 
 
 for（std :: size_t Lsize = 1; Lsize <= 4; ++ Lsize）
 {
 for（unsigned i = 0; i  {
 std :: size_t k = std :: min（Lsize，data [i] .size（））; 
 
 do 
 {
 std :: set< int> n_k（data [i] .begin（），data [i] .begin（）+ k）; 
 ++ counting [n_k]; 
} 
 while（next_combination（data [i] .begin（），data [i] .begin（）+ k，data [i] .end（） 
} 
} 
  

I used the code in this topic http://stackoverflow.com/a/5097100/3617657

and I edit it little bit to work on std::vector<std::vector<int>> instead std::vector<int>

K in my case has different values (from 1- to 4), instead only one single value

Example: my data

1 2 3 4
1 2 4
1 3

if k=3, Then for each line in my data, n choose k=

123
124
134
234

124

13

but I want my result in map, where the value represents the frequency of subset as:

(123, 1)
(124, 2)
(134, 1)
(234, 1)

(13, 1)

This is my code:

std::vector<std::vector<int>> data;

std::map <int, set<int>> CandidateSet;
typedef std::pair<set<int>, int> combo;
std::map <int, combo> CandidateSup;





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::vector<int> inner;
        int info;

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

        data.push_back(inner);
    }
}



int main()
{
    ScanData();
    std::size_t k = 0;
    int j = 0;
    int c = 0;
    int supp = 1;
    int Lsize = 1; 
    while (Lsize <= 4) 
    {
        for (unsigned i = 0; i < data.size(); ++i)
        {
            std::vector<int>::iterator items = data[i].begin();
            if (Lsize > data[i].size())
                k = data[i].size();
            else
                k = Lsize;

            do
            {
                for (std::vector<int>::iterator items = data[i].begin(); j < k; ++items)
                {
                    CandidateSet[c].insert(*items);
                    ++j;
                }

                ++c;
                std::cout << "\n";
                j = 0;

            } 
            while (next_combination(data[i].begin(), data[i].begin() + k, data[i].end()));



        /****************************************************************************************************************************** 
            //here my problem
            // check if the (next_combination) is already exist in CandidateSet, if yes add one to existing support

            auto it = CandidateSet.begin();
            set <int> A = it->second;
            set <int> B;

            B = CandidateSet[*items]; // I don't know how to set be as the next_combination


            while (it != CandidateSet.end())
            { // if it found 
                if (!(A < B) && !(B < A))
                {
                    CandidateSup[*items] = std::make_pair(A, ++supp);
                    break;
                }
                else
                { // if not found yet
                    ++it; 
                    A = it->second;
                }
            }//  end while

            // if it is not exist, add this new set with support =1
            ++c;
            CandidateSup[c] = std::make_pair(B, supp);
        /******************************************************************************************************************************/

        }
        ++Lsize;

    }

    data.clear();





    system("PAUSE");
    return 0;
}

This "combination.h"

template <typename Iterator>
inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
    /* Credits: Thomas Draper */
    if ((first == last) || (first == k) || (last == k))
        return false;
    Iterator itr1 = first;
    Iterator itr2 = last;
    ++itr1;
    if (last == itr1)
        return false;
    itr1 = last;
    --itr1;
    itr1 = k;
    --itr2;
    while (first != itr1)
    {
        if (*--itr1 < *itr2)
        {
            Iterator j = k;
            while (!(*itr1 < *j)) ++j;
            std::iter_swap(itr1, j);
            ++itr1;
            ++j;
            itr2 = k;
            std::rotate(itr1, j, last);
            while (last != j)
            {
                ++j;
                ++itr2;
            }
            std::rotate(k, itr2, last);
            return true;
        }
    }
    std::rotate(first, k, last);
    return false;
}

解决方案

The following may help: (https://ideone.com/5EPuGd)

std::map<std::set<int>, int> counts;

for (std::size_t Lsize = 1; Lsize <= 4; ++Lsize)
{
    for (unsigned i = 0; i < data.size(); ++i)
    {
        std::size_t k = std::min(Lsize, data[i].size());

        do
        {
            std::set<int> n_k(data[i].begin(), data[i].begin() + k);
            ++counts[n_k];
        }
        while (next_combination(data[i].begin(), data[i].begin() + k, data[i].end()));
    }
}

这篇关于n选择k条件的实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！