首页 > 试题广场 >

特征排列组合

[编程题]特征排列组合
  • 热度指数:527 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
机器学习问题中,经常有很多抽取的特征,而特征之间往往可以通过组合,得到更抽象有用的特征。比如性别特征-(男,女),和职业特征(程序员,美工,策划),可以交叉出(男-程序员,男-美工,男-策划,女-程序员,女-美工,女-策划),更抽象的特征可以表达出一些复合的语义和对数据的刻画,往往在模型中会获得意想不到的作用。

本题需要你也开发一个类似的功能,将输入的各种特征进行自动的排列组合。

输入描述:
输入n,表示总共有多少组不同的特征,1<=n<=100
下面有n行,每一行特征为该组的所有取值,用空格区分, 每一行的特征值数量不大于100,每个特征值为英文或者数字组合成的字符串


输出描述:
输出为排列组合后的所有组合值,每个组合值为一行,不同组的特征值之间用"-"连接,显示顺序保持的原特征的显示顺序关系(参照例子)
示例1

输入

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;

}

发表于 2021-04-10 11:59:02 回复(0)
import sys
 
n = int(input())
features = []
for _ in range(n):
    features.append(input().split())
 
l = features[-1].copy()
for i in range(n - 2, -1, -1):
    tmp = []
    for f in l:
        for cur in features[i]:
            tmp.append(cur + "-" + f)
    l = tmp
for ans in l:
    print(ans)

发表于 2023-08-26 17:29:10 回复(0)
# 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;
}

宝儿学会了吗
发表于 2022-07-14 21:06:51 回复(0)
倒序dfs即可 .
#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;
}


发表于 2022-07-05 19:28:31 回复(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;
}

发表于 2022-06-15 15:53:35 回复(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);

}
发表于 2022-03-26 00:05:07 回复(0)
dfs
#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;
}


发表于 2022-03-25 21:57:22 回复(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。
发表于 2021-03-29 21:21:00 回复(0)
#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;
}

编辑于 2021-02-28 19:20:27 回复(1)
沃日,输出顺序不对也是错的,即便和答案一样
#include<iostream>
#include<vector>
using namespace std;

void find(vector<string> &ret,string &cur, vector<vector<string>> &strs, int idx, const int &n )
{
    if(idx>=n){ret.push_back(cur);return ;}
    for(int i=0;i<strs[idx].size();i++)
    {
        if(cur.size()==0)    
        {
            cur +=strs[idx][i];
            find(ret, cur, strs, idx+1, n);
            cur = "";//cur.substr(0, cur.size()-strs[idx][i].size());
        }
        else 
        {
            cur =cur +"-"+strs[idx][i];
            find(ret, cur, strs, idx+1, n);
            cur = cur.substr(0, cur.size()-strs[idx][i].size()-1);
        }
        
    }
}
int main()
{
    int n ;
    cin>>n;
    vector<string> ret;
    vector<vector<string>> strs;
    strs.assign(n, {});
    string t,word;
    getline(cin, t);
    for(int i=0;i<n;i++)
    {
        
        t.clear();word.clear();
        getline(cin, t);
        for (char c : t) 
        {
          if (c != ' ') 
          {
            word.push_back(c);
            continue;
          }
          strs[i].push_back(move(word));
          word.clear();t.clear();
        }
        strs[i].push_back(move(word));
    }
    //vector<string> ret;
    ret.clear();
    string cur = "";
    find(ret,cur,strs, 0, n);
    //cout<<strs[2].size()<<endl;
    int k = strs[0].size();
    int n_r= ret.size();
    for(int i=0;i<(n_r/k);i++)    
    {
        for(int j =0;j<k;j++){cout<<ret[i+j*(n_r/k)]<<endl;}
        
    }
    return 0;
}
发表于 2021-01-18 22:34:46 回复(0)