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(); : }
|
|