s*c
发帖数: 95 | 1 Print all combinations of M members of a set of N elements in a sequence
such that each set can be obtained from the previous set by deleting one
member and adding one member. | c****p
发帖数: 6474 | 2 google gray code
【在 s*c 的大作中提到】
: Print all combinations of M members of a set of N elements in a sequence
: such that each set can be obtained from the previous set by deleting one
: member and adding one member.
| p*****2
发帖数: 21240 | 3
这个是gray code吗？
【在 c****p 的大作中提到】
: google gray code
| c****p
发帖数: 6474 | 4 题看错了。
【在 p*****2 的大作中提到】
:
: 这个是gray code吗？
| w****x
发帖数: 2483 | 5
delete 一个再加一个不就是修改一个吗~~
【在 p*****2 的大作中提到】
:
: 这个是gray code吗？
| p*****2
发帖数: 21240 | 6 这题前半部作为面试题就够了。加上后半边不容易呀。面试碰到不好搞 | p*****2
发帖数: 21240 | 7 把所有的set连成图，然后变成找一个路径cover所有node？ | p********s
发帖数: 37 | 8 有个非常浪费空间的递推，大牛们看看对不：
设cmb(n,m)为从n个里面选m个并按要求的顺序解集合，其中每个解用一个长度n的
bitset，其中m个1表示元素是否出现，比如
(3,2) 011 110 101
(4,2) 0011 0110 0101 1100 1010 1001
有
cmb(n,n) = n个1
cmb(n,0) = n个0
设[cmb(n,m)+'a']为给所有cmb(n,m)末尾加个a(1或0),
设~[x]为[x]的倒序,有
cmb(n,m) = [cmb(n-1,m)+'0'] + ~[cmb(n-1,m-1)+'1']
代码如下
vector all[50][50];
void init() {
for(int i = 1; i < 20; i++) {
all[i][0].push_back(0);
all[i][i].push_back((1 << i) - 1);
for(int j = 1; j < i; j++) {
for(int k = 0; k < all[i-1][j].size(); k++)
all[i][j].push_back(all[i-1][j][k] << 1);
for(int k = all[i-1][j-1].size()-1; k >=0; k--)
all[i][j].push_back((all[i-1][j-1][k] << 1) + 1);
}
}
}
(1,1) 1
(2,1) 01 10
(2,2) 11
(3,1) 001 010 100
(3,2) 011 110 101
(3,3) 111
(4,1) 0001 0010 0100 1000
(4,2) 0011 0110 0101 1100 1010 1001
(4,3) 0111 1101 1110 1011
(4,4) 1111
(5,1) 00001 00010 00100 01000 10000
(5,2) 00011 00110 00101 01100 01010 01001 11000 10100 10010 10001
(5,3) 00111 01101 01110 01011 11001 11010 11100 10101 10110 10011
(5,4) 01111 11011 11110 11101 10111
(5,5) 11111
(6,1) 000001 000010 000100 001000 010000 100000
(6,2) 000011 000110 000101 001100 001010 001001 011000 010100 010010
010001 110000 101000 100100 100010 100001
(6,3) 000111 001101 001110 001011 011001 011010 011100 010101 010110
010011 110001 110010 110100 111000 101001 101010 101100 100101 100110 100011
(6,4) 001111 011011 011110 011101 010111 110011 110110 110101 111100
111010 111001 101011 101110 101101 100111
(6,5) 011111 110111 111101 111110 111011 101111
(6,6) 111111 | p*****2
发帖数: 21240 | 9
你太牛了。膜拜一下。只是还有一点没想明白。
cmb(n,m) = [cmb(n-1,m)+'0'] + ~[cmb(n-1,m-1)+'1']
怎么证明第一部分得最后一个和第二部分得第一个是连续得？
【在 p********s 的大作中提到】
: 有个非常浪费空间的递推，大牛们看看对不：
: 设cmb(n,m)为从n个里面选m个并按要求的顺序解集合，其中每个解用一个长度n的
: bitset，其中m个1表示元素是否出现，比如
: (3,2) 011 110 101
: (4,2) 0011 0110 0101 1100 1010 1001
: 有
: cmb(n,n) = n个1
: cmb(n,0) = n个0
: 设[cmb(n,m)+'a']为给所有cmb(n,m)末尾加个a(1或0),
: 设~[x]为[x]的倒序,有
| p********s
发帖数: 37 | 10 二爷法眼无差，俺typo了，后面那半应该先倒转再+1
大体思路就是保证任何一个cmb(n,m)的第一个串开头为m个1，后面都是0；最后一个串
开头为m-1个1，后面除末尾都是零，末尾为1。cmb(2,1)=[10，01]
那对cmb(n-1,m)的第一个就是
(m个1)+(一堆0)
....
最后一个
(m-1个1)+(一堆0)+(1)
对cmb(n-1,m-1)的最后一个就是
(m-2个1)+(一堆0)+(1)
...
第一个就是
(m-1个1)+(一堆0)
[cmb(n-1,m)+0]和[~cmb(n-1,m-1])+1]正好能接上，并且保持之前的性质
-- | p*****2
发帖数: 21240 | 11
大概能推出来。不过这题对我来说太难了，面试碰到肯定挂了。你也太牛了。过几天又
是个大满贯得人物了。
【在 p********s 的大作中提到】
: 二爷法眼无差，俺typo了，后面那半应该先倒转再+1
: 大体思路就是保证任何一个cmb(n,m)的第一个串开头为m个1，后面都是0；最后一个串
: 开头为m-1个1，后面除末尾都是零，末尾为1。cmb(2,1)=[10，01]
: 那对cmb(n-1,m)的第一个就是
: (m个1)+(一堆0)
: ....
: 最后一个
: (m-1个1)+(一堆0)+(1)
: 对cmb(n-1,m-1)的最后一个就是
: (m-2个1)+(一堆0)+(1)
| d****n
发帖数: 233 | 12 Combine(T A[], N, M) {
T B[] = new T[M];
for(int i = 0; i < M; ++i) {
B[i] = A[i];
}
CombineHelper(A, B, N, M, M);
}
CombineHelper(T A[], T B[], N, M, current) {
print(B, M);
if (current >= N) return;
T tmp;
for(int i = 0; i < M; i++) {
tmp = B[i];
B[i] = A[current]
CombineHelper(A, B, N, M, current + 1);
B[i] = tmp;
}
}
|
|
