由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Subset of size m Problem
相关主题
facebook 一面google search hint words data structure
也问 Bloomberg 的 C++ online assessment test (FSD)微软面试的小体会
G家老年和F家E5,package有多少?intern/offer汇报
谁知道 Baidu AI lab technical phone interview questions[合集] intern/offer汇报
a perl software engineer is needed in Boston area[合集] 公布几道变态的面试题。
job opening in an investment bankPhD Interview 问题总结
投行Quant组招人,有兴趣请投条Offer is coming奉上Onsite以及电面的一些问题
帮人找个desk quant developerMath Interview Question Help
相关话题的讨论汇总
话题: output话题: subset话题: int话题: size话题: vector
进入JobHunting版参与讨论
1 (共1页)
x*******5
发帖数: 152
1
请教各位大牛一个问题:
Problem: Output all subsets of size of m from an array
Solution Hints: String permutation Problem variant
Python Codes:
def Subset_m(v,l,m,output):
"Find all subsets of an array v of size m, need fixing"
if l==m:
print output
return
for i in range(l,len(v)):

output[l]=v[i]
Subset_m(v,l+1,m,output)
C++ Codes:
/*Description: output all the subset of size m
Input:vector v, int m,int l, vector& output
Output: void
*/
void Pearl::SubArrayS_size_m(vector v, int m,int l, vector& output
){
if(l==m){
for(int i=0;i cout< cout<
return;
}
else{
for(int i=l;i output[l]=v[i];
SubArrayS_size_m(v,m,l+1,output);
}
}
}
Test Case:
v=[1,2,3]
output=[0 for i in range(2)]
Pearl.Subset_m(v, 0, 2, output)
Output:
[1, 2]
[1, 3]
[2, 2]
[2, 3]
[3, 2]
[3, 3]
问题:总是输出[2,2] ,[3,3]这种不对的答案,目前不知道如何修改是好,请教各位大
k*****y
发帖数: 744
2
you might need to do a swap after you pick i, and a swap back after the
recursive call.

【在 x*******5 的大作中提到】
: 请教各位大牛一个问题:
: Problem: Output all subsets of size of m from an array
: Solution Hints: String permutation Problem variant
: Python Codes:
: def Subset_m(v,l,m,output):
: "Find all subsets of an array v of size m, need fixing"
: if l==m:
: print output
: return
: for i in range(l,len(v)):

x*******5
发帖数: 152
3
def Subset_m(v,l,m):
"Find all subsets of an array v of size m, need fixing"
if l==m:
print v[:m]
return
for i in range(l,len(v)):

v[l],v[i]=v[i],v[l]
Subset_m(v,l+1,m)
v[l],v[i]=v[i],v[l]
Output:
[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 2]
[3, 1]
感谢,现在正确了,其实就是string permutation的变体,谢谢

【在 k*****y 的大作中提到】
: you might need to do a swap after you pick i, and a swap back after the
: recursive call.

H*****1
发帖数: 4815
4

~~~~~~~~~~~~~~~~~~~~~~~~~~
这个循环不应该有
应该是对m[l]分支,加入或者不加入这个元素

【在 x*******5 的大作中提到】
: 请教各位大牛一个问题:
: Problem: Output all subsets of size of m from an array
: Solution Hints: String permutation Problem variant
: Python Codes:
: def Subset_m(v,l,m,output):
: "Find all subsets of an array v of size m, need fixing"
: if l==m:
: print output
: return
: for i in range(l,len(v)):

p*i
发帖数: 411
5
不对
[2, 3] 跟[3, 2]是一样的,注意是set/集合不是permutation

【在 x*******5 的大作中提到】
: def Subset_m(v,l,m):
: "Find all subsets of an array v of size m, need fixing"
: if l==m:
: print v[:m]
: return
: for i in range(l,len(v)):
:
: v[l],v[i]=v[i],v[l]
: Subset_m(v,l+1,m)
: v[l],v[i]=v[i],v[l]

k*****y
发帖数: 744
6
Thanks, good point. How about
========================================
def Subset_m(v,b,l,m,output):
if l==m:
print output
return
for i in range(b,len(v)-(m-(l+1))):
output[l]=v[i]
Subset_m(v,i+1,l+1,m,output)
========================================
Add a variable b to indicate where to start for the current selection.

【在 p*i 的大作中提到】
: 不对
: [2, 3] 跟[3, 2]是一样的,注意是set/集合不是permutation

x*******5
发帖数: 152
7
没有办法了,只能上这个了
def Subset_m(v,l,m,result):
"Find all subsets of an array v of size m, need fixing"
if l==m:
if sorted(v[:m]) not in result:
print v[:m]
result.append(sorted(v[:m]))

return
for i in range(l,len(v)):

v[l],v[i]=v[i],v[l]
Subset_m(v,l+1,m,result)
v[l],v[i]=v[i],v[l]
Test:
v=[1,2,3]
Output:
[1, 2]
[1, 3]
[2, 3]
这个应该对的了,用东西记录已经存在的subset(因为是set,所以要sorted存储)
l*****a
发帖数: 14598
8
void GetSubset(T array[],size_t size,int start,size_t target,vector&vec)
{
if (vec.size()==target) {PRINT; return;}
if(start ==size) return;
for(int i=start;i {
vec.push_back(array[i]);
GetSubset(array,size,i+1,target,vec);
vec.pop_back();
}
return;
}

【在 x*******5 的大作中提到】
: 请教各位大牛一个问题:
: Problem: Output all subsets of size of m from an array
: Solution Hints: String permutation Problem variant
: Python Codes:
: def Subset_m(v,l,m,output):
: "Find all subsets of an array v of size m, need fixing"
: if l==m:
: print output
: return
: for i in range(l,len(v)):

x*******5
发帖数: 152
9
谢谢大牛指导,但是好像C++的还是不work
void Pearl::GetSubset(vector& array, int target,int start,vector&
vec){
if (vec.size()==target){

Pearl::Print(vec);
return;
}
if (start==array.size()) return;
for (int i=start;i vec.push_back(array[i]);
GetSubset(array,target,start+1,vec);
vec.pop_back();
}
return;
}
测试:
int a[]={1,2,3};
vector v(a,a+3);
vector vec;
Pearl::GetSubset(v,2,0,vec);
Output:
1 2
1 3
2 2
2 3
3 2
3 3

【在 l*****a 的大作中提到】
: void GetSubset(T array[],size_t size,int start,size_t target,vector&vec)
: {
: if (vec.size()==target) {PRINT; return;}
: if(start ==size) return;
: for(int i=start;i: {
: vec.push_back(array[i]);
: GetSubset(array,size,i+1,target,vec);
: vec.pop_back();
: }

1 (共1页)
进入JobHunting版参与讨论
相关主题
Math Interview Question Helpa perl software engineer is needed in Boston area
电面后,hr发了两道题,请教高手job opening in an investment bank
一道caeerCup上的难算法题投行Quant组招人,有兴趣请投条
Amazon算法问题请教帮人找个desk quant developer
facebook 一面google search hint words data structure
也问 Bloomberg 的 C++ online assessment test (FSD)微软面试的小体会
G家老年和F家E5,package有多少?intern/offer汇报
谁知道 Baidu AI lab technical phone interview questions[合集] intern/offer汇报
相关话题的讨论汇总
话题: output话题: subset话题: int话题: size话题: vector