又一个卧底暴露了 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

又一个卧底暴露了

又一个卧底暴露了# Joke - 肚皮舞运动

x*52011-11-18 08:11

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;icout<cout<
return;
}
else{
for(int i=l;ioutput[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]这种不对的答案，目前不知道如何修改是好，请教各位大
牛

a*52011-11-18 08:11

2 楼

k*y2011-11-18 08:11

3 楼

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*52011-11-18 08:11

4 楼

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*12011-11-18 08:11

5 楼

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

【在 x*******5 的大作中提到】

p*i2011-11-18 08:11

6 楼

不对
[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*y2011-11-18 08:11

7 楼

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*52011-11-18 08:11

8 楼

没有办法了，只能上这个了
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*a2011-11-18 08:11

9 楼

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 的大作中提到】

x*52011-11-18 08:11

10 楼

谢谢大牛指导，但是好像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;ivec.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();
: }