机器学习问题中,经常有很多抽取的特征,而特征之间往往可以通过组合,得到更抽象有用的特征。比如性别特征-(男,女),和职业特征(程序员,美工,策划),可以交叉出(男-程序员,男-美工,男-策划,女-程序员,女-美工,女-策划),更抽象的特征可以表达出一些复合的语义和对数据的刻画,往往在模型中会获得意想不到的作用。
本题需要你也开发一个类似的功能,将输入的各种特征进行自动的排列组合。
输入n,表示总共有多少组不同的特征,1<=n<=100下面有n行,每一行特征为该组的所有取值,用空格区分, 每一行的特征值数量不大于100,每个特征值为英文或者数字组合成的字符串
输出为排列组合后的所有组合值,每个组合值为一行,不同组的特征值之间用"-"连接,显示顺序保持的原特征的显示顺序关系(参照例子)
3 man woman coder gamer painter phd
man-coder-phd woman-coder-phd man-gamer-phd woman-gamer-phd man-painter-phd woman-painter-phd
2*3*1=6行,保持原特征顺序
#include <iostream> using namespace std; #include <vector> #include <string> #include <map> #include <boost/algorithm/string.hpp> vector<string>Split(const string&s,const string c) { vector<string>res; int pos1=0,pos2=s.find_first_of(c); while(pos2!=string::npos) { if(pos2!=pos1) res.push_back(s.substr(pos1,pos2-pos1)); pos1=pos2+1; pos2=s.find_first_of(c,pos1); } if(pos1!=s.size()){ res.push_back(s.substr(pos1)); } return res; } void zuhe(vector<string>&res,map<int,vector<string>> mp,string cur,int index){ if(index<0) { res.push_back(cur); return; } for(int i=0;i<mp[index].size();i++) { string t=cur; cur=mp[index][i]+cur; if(index>0) cur='-'+cur; zuhe(res,mp,cur,index-1); cur=t; } } int main() { int N; cin>>N; map<int,vector<string>> mp; string line; int i=0; string t; cin.ignore(); for(int i=0;i<N;i++) { getline(cin,line); mp[i]=Split(line," "); } vector<string>res; string cur; zuhe(res,mp,cur,mp.size()-1); for(auto &x:res) cout<<x<<endl; }
# include <bits/stdc++.h> using namespace std; //# pragma GCC optimize("Ofast") //# pragma GCC optimize ("unroll-loops") //# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") # define rep(i,a,n) for (int i=a; i<n; ++i) # define per(i,a,n) for (int i=a-1; i>=n; --i) # define bug cerr<<"hi"<<endl; # define eb emplace_back # define pb push_back # define mp make_pair # define mt make_tuple # define all(x) (x).begin(), (x).end() # define SZ(x) (int)x.size() # define fi first # define se second # define INF 1000000001 using Vi = vector<int>; using i64 = long long; using ll = long long; using Pi = pair<int, int>; using Ti = tuple<int, int, int>; mt19937 mrand(time(0)); int rnd(int x) {return mrand()%x;} int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector a(n, vector<string>()); rep(i,0,n) { string s; while (cin >> s) { a[i].eb(s); if (cin.get() == '\n') break; } } function<void(int, vector<string>&)> sol = [&](int x, vector<string>& ans) { if (x < 0) { per(i,n,0) cout << ans[i] << "-\n"[i == 0]; return ; } for (auto& i: a[x]) { ans.eb(i); sol(x - 1, ans); ans.pop_back(); } }; vector<string> ans; sol(n - 1, ans); return 0; }宝儿学会了吗
#include <bits/stdc++.h> using namespace std; using ll = long long; int n; vector<vector<string>> feature; vector<int> arr; void dfs(int idx) { if (idx == -1) { for (int i = 0; i < n; ++i) { cout << feature[i][arr[i]]; if (i + 1 < n) cout << '-'; } cout << '\n'; } else { for (int i = 0, k = feature[idx].size(); i < k; ++i) { arr[idx] = i; dfs(idx - 1); } } } int main() { string str, temp; cin >> n, feature.resize(n), cin.get(); for (auto &feat : feature) { getline(cin, str); stringstream ss(str); while (ss >> temp) feat.push_back(move(temp)); } arr.resize(n), dfs(n - 1); return 0; }
#include <bits/stdc++.h> using namespace std; void helper(vector<vector<string>>& features, vector<string>& res, string cur, int index) { if (index < 0) { res.push_back(cur); return; } for (auto feature : features[index]) { string next; if (index > 0) next = '-' + feature + cur; else next = feature + cur; helper(features, res, next, index - 1); } } int main() { int n; cin >> n; vector<vector<string>> features(n); for (int i = 0; i < n; i++) { string buf; while (cin >> buf) { features[i].push_back(buf); if (cin.get() == '\n') break; } } string cur = ""; vector<string> res; helper(features, res, cur, features.size() - 1); for (auto& item : res) cout << item << endl; return 0; }
这个题稍微需要注意的一点就是它的输出顺序,观察可以发现其实就是倒序dfs遍历的结果,再逆序输出。“负负得正”
#include <iostream> #include <string> #include <vector> using namespace std; int n; void helper (const vector<vector<string>>& features, int cur, vector<string>& ans) { if (cur < 0) { for (int i = n - 1; i >= 1; i--) cout<<ans[i]<<"-"; cout<<ans[0]<<endl; return; } for (auto s : features[cur]) { ans.push_back(s); helper(features, cur - 1, ans); ans.pop_back(); } } int main() { cin>> n; vector<vector<string>> features(n); for (int i = 0; i < n; i++) { do{ string temp; cin>>temp; features[i].push_back(temp); } while (cin.get() != '\n'); } vector<string> ans; helper(features, n - 1, ans); }
#include <bits/stdc++.h> using namespace std; void dfs(const vector<vector<string>> &m, string path, int depth) { if(depth < 0) { cout << path << endl; return; } for(int i = 0;i < m[depth].size();i++) dfs(m, depth == m.size()-1 ? m[depth][i] : m[depth][i]+"-"+path, depth-1); } int main() { int n; cin >> n; vector<vector<string>> feas(n, vector<string>()); for(int i = 0;i < n;i++) { string tmp; while(cin >> tmp) { feas[i].push_back(tmp); if(cin.get() == '\n')break; } } //开始dfs string path; dfs(feas, path, feas.size()-1); return 0; }
#include<bits/stdc++.h> using namespace std; void bfs(vector<vector<string>> &data,int pos,vector<string> &ans,string tmp){ if(pos == -1){ int t = tmp.size(); tmp = tmp.substr(0,t-1); ans.push_back(tmp); return; } for(int i=0;i<data[pos].size();i++){ bfs(data,pos-1,ans,data[pos][i]+"-"+tmp); } } int main(){ int n; cin>>n; cin.ignore(); vector<vector<string>> data(n); for(int i=0;i<n;i++){ string s1,tmp; getline(cin,s1); stringstream ss(s1); while(ss>>tmp){ data[i].push_back(tmp); } } vector<string> ans; bfs(data,n-1,ans,""); for(string &s:ans) cout<<s<<endl; system("pause"); return 0; }由于是BFS的顺序,所以倒序DFS。
#include<iostream> #include<string> #include<vector> using namespace std; int main(){ int n, amount = 1; cin>>n; vector> helper(n); for(int i = 0; i < n; ++i){ string str; char c; int count = 0; while((cin>>str).get(c)){ ++count; helper[i].push_back(str); if(c == '\n') break; } amount *= count; } vector ans(amount); for(int index = 0; index < amount; ++index){ int prod = 1; for(int i = 0; i < n; ++i){ int sz = helper[i].size(); ans[index] += helper[i][index / prod % sz]; ans[index] += '-'; prod *= sz; } } for(int i = 0; i < amount; ++i){ string str = ans[i]; str.erase(str.size() - 1); cout<<str<<endl; } return 0; }