k*******p
发帖数: 219 | 1 我无耻，我少写了个条件
要保证B数组也是升序排列的。
新题：
one integer array A with ascending order, for example 1 ,2 ,3,4, please
generate another array B with any sum of any 3
different numbers picked from the A with ascending order, for example for 1,2,3,4, the result is
(1+2+3),(1＋2＋4),(1＋3＋4),(2＋3＋4）“
原来的题：
”
one integer array A with ascending order, for example 1 ,2 ,3,4, please
generate another array B with any 3
different numbers picked from the A, for example for 1,2,3,4, the result is
(1+2+3),(1,2,4),(1,3,4),(2,3,4）“
谢谢。 | k*******p
发帖数: 219 | | g*****k
发帖数: 623 | 3 isn't this just a recursive function with prototype like
f(int A[], int lengthA, int B[], int lengthB, int cur_pos)
when you choose index for B[cur_pos], you choose one from
B[cur_pos - 1]+1 to lengthA.
is
【在 k*******p 的大作中提到】
: 另外，如果扩展到 k位数呢？
| k*******p
发帖数: 219 | | g**********y
发帖数: 14569 | 5 run(new int[]{1, 2, 3, 4}, 3, 0, "");
public void run(int[] a, int n, int p, String result) {
if (n == 0) {
System.out.println(result);
return;
}
for (int i=p; i<=a.length-n; i++) {
run(a, n-1, i+1, result + " " + a[i]);
}
} | x********o
发帖数: 519 | 6 here is the C++ code:
#include
#include
#include
using namespace std;
void print_vector(const vector &v){
vector::const_iterator iter=v.begin();
while(iter!=v.end()){
cout<<*iter<<" ";
++iter;
}
cout<
}
void subset(vector v, vector sub, int size,set > &s){
if(sub.size()==size){
sort(sub.begin(),sub.end());
s.insert(sub);
return;
}
vector::iterator iter=v.begin();
size_t l=v.size();
for(int i=0;i
vector temp(v);
vector subs(sub);
temp.erase(temp.begin()+i);
subs.push_back(v[i]);
subset(temp,subs,size,s);
}
}
int main(){
int a[]={1,2,3,4};
vector v(a,a+4);
vector sub;
set > s;
subset(v,sub,3,s);
set >::const_iterator iter=s.begin();
while(iter!=s.end()){
print_vector(*iter);
++iter;
}
return 0;
} | k*******p
发帖数: 219 | 7 题目我写错了，已经修改。这个递归写的很neat 赞一个。
【在 g**********y 的大作中提到】
: run(new int[]{1, 2, 3, 4}, 3, 0, "");
: public void run(int[] a, int n, int p, String result) {
: if (n == 0) {
: System.out.println(result);
: return;
: }
:
: for (int i=p; i<=a.length-n; i++) {
: run(a, n-1, i+1, result + " " + a[i]);
: }
| f****4
发帖数: 1359 | 8 就是 n choose k的combination啊；把打印替换成sum->array
只要从最小数开始，就能符合结果递增 | k*******p
发帖数: 219 | 9 这样的话，可以全部打出来，但你保证不了排序，比如 a数组是 {1, 8, 9, 10,26} 从
最小数一直打，结果是：
1 8
1 9
1 10
1 26
8 9（错误）
8 10
8 26
9 10
9 26
10 26 | f****4
发帖数: 1359 | 10 还有别的要求没有？
没有的话就再搞个BST，算出来的sum insert进去，最后中续遍历输出
要是在combine过程当中搞的话，要想想 | | | h*********n
发帖数: 11319 | 11 8,9 怎么错了啊？b的排序不是这么拍
的么？
import copy
def select(array, start, depth):
if depth==0:
print array
else:
for i in range(start, len(array)):
arrayCopy = copy.deepcopy(array)
del arrayCopy[i]
select(arrayCopy, i, depth-1)
def select2(array, string, start, depth):
if depth==0:
print string
else:
for i in range(start, len(array)):
string.append(array[i])
select2(array, string, i+1, depth-1)
del string[len(string)-1]
#select([1,2,3,4,5,6], 0, 2) #倒着打印
select2([1,2,3,4,5,6], [], 0, 3) #正着打印
【在 k*******p 的大作中提到】
: 这样的话，可以全部打出来，但你保证不了排序，比如 a数组是 {1, 8, 9, 10,26} 从
: 最小数一直打，结果是：
: 1 8
: 1 9
: 1 10
: 1 26
: 8 9（错误）
: 8 10
: 8 26
: 9 10
| s*****y
发帖数: 897 | 12 co-ask.
【在 h*********n 的大作中提到】
: 8,9 怎么错了啊？b的排序不是这么拍
: 的么？
:
: import copy
: def select(array, start, depth):
: if depth==0:
: print array
: else:
: for i in range(start, len(array)):
: arrayCopy = copy.deepcopy(array)
| f****4
发帖数: 1359 | | d*******l
发帖数: 338 | 14 题目的意思相当于有序打印集合A所有大小为3的子集，代码如下：
void run(int a[], int n, int m, vector &subset)
{
if(n < m) return ;
if(m == 0) {
for(int i = 0; i < subset.size(); i++)
cout << subset[i] << " ";
cout << endl;
return ;
}
subset.push_back(a[0]);
run(a+1, n-1, m-1, subset);
vector::iterator it;
subset.erase(subset.begin() + subset.size() - 1);
run(a+1, n-1, m, subset);
}
int a[10] = {1,8,9,10,26};
int main() {
vector v(0);
run(a, 5, 2, v);
return 0;
}
初始传入的参数是数组地址a，数组大小n，要打印的子集的大小m以及一个空的vector
。程序将按顺序打印所有子集。其实就是递归的先打印包含当前数，剩下集合所有大小
为m-1的子集，和不包含当前数，剩下集合大小为m的子集。 | g*****k
发帖数: 623 | 15 Why you people like to decrement m instead of incrementing m?
By increment, you can get rid of push_back and erase, if you reserve size m
for subset.
Thus you can access subset[m] each time and don't need to erase elements.
题目的意思相当于有序打印集合A所有大小为3的子集，代码如下：
void run(int a[], int n, int m, vector &subset)
{
if(n < m) return ;
if(m == 0) {
for(int i = 0; i < subset.size(); i++)
cout << subset[i] << " ";
cout << endl;
return ;
}
subset.push_back(a[0]);
run(a+1, n-1, m-1, subset);
vector::iterator it;
subset.erase(subset.begin() + subset.size() - 1);
run(a+1, n-1, m, subset);
}
int a[10] = {1,8,9,10,26};
int main() {
vector v(0);
run(a, 5, 2, v);
return 0;
}
初始传入的参数是数组地址a，数组大小n，要打印的子集的大小m以及一个空的vector
。程序将按顺序打印所有子集。其实就是递归的先打印包含当前数，剩下集合所有大小
为m-1的子集，和不包含当前数，剩下集合大小为m的子集。
【在 d*******l 的大作中提到】
: 题目的意思相当于有序打印集合A所有大小为3的子集，代码如下：
: void run(int a[], int n, int m, vector &subset)
: {
: if(n < m) return ;
: if(m == 0) {
: for(int i = 0; i < subset.size(); i++)
: cout << subset[i] << " ";
: cout << endl;
: return ;
: }
| k*******p
发帖数: 219 | 16 1＋26 比 8＋9 大了，b数组每个数是三个a数组数字的和。b也要保持升序。
【在 h*********n 的大作中提到】
: 8,9 怎么错了啊？b的排序不是这么拍
: 的么？
:
: import copy
: def select(array, start, depth):
: if depth==0:
: print array
: else:
: for i in range(start, len(array)):
: arrayCopy = copy.deepcopy(array)
| d*******l
发帖数: 338 | 17 我想这是因为递减m的话就可以少加个参数，因为直接判断是否为0即可。这题大家都没
有优先考虑效率的问题，似乎都是想尽量写简洁，真要从效率出发，肯定不能用vector
，直接用个数组就行，这时需要多加个参数标记当前的位置，数组的push和pop体现在
位置的移动，就不需要额外开销了。
m
【在 g*****k 的大作中提到】
: Why you people like to decrement m instead of incrementing m?
: By increment, you can get rid of push_back and erase, if you reserve size m
: for subset.
: Thus you can access subset[m] each time and don't need to erase elements.
:
: 题目的意思相当于有序打印集合A所有大小为3的子集，代码如下：
: void run(int a[], int n, int m, vector &subset)
: {
: if(n < m) return ;
: if(m == 0) {
| g*****k
发帖数: 623 | 18 哦，原来是为了简洁啊。明白了
vector
【在 d*******l 的大作中提到】
: 我想这是因为递减m的话就可以少加个参数，因为直接判断是否为0即可。这题大家都没
: 有优先考虑效率的问题，似乎都是想尽量写简洁，真要从效率出发，肯定不能用vector
: ，直接用个数组就行，这时需要多加个参数标记当前的位置，数组的push和pop体现在
: 位置的移动，就不需要额外开销了。
:
: m
|
|
