n选择k条件的实现

本文介绍了n选择k条件的实现的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我使用了本主题中的程式码 stackoverflow/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 此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; }

解决方案

ideone/5EPuGd ）

std :: map< std :: set< int>，int>计数; for（std :: size_t Lsize = 1; Lsize <= 4; ++ Lsize） { for（unsigned i = 0; i

I used the code in this topic stackoverflow/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: (ideone/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())); } }