i******y
发帖数: 191 | 1 任意给定一个二进制数，比如10111，现在要打印出所有的非零位1的个数和等于k的二
进制数。
说得比较饶……
就比如给你10111，给定K=2，也就是说1的个数和只能等于2
那么就要输出：
10100， 10010， 10001， 00110， 00101， 00011，大概就是C（4,2）= 6这么多种组
合。
再比如给定10111，K=3
就要输出：
10110, 10101， 10011， 00111，一共C（4,3）= 4种.
我怎么想都觉得这个方法搞下去是指数级的(或者阶乘级的)复杂度，求简单的办法？ |
b******n
发帖数: 4509 | 2 其实就是 a 个 0， b 个 1 有多少种排列，a b 已知
最小的排列是 0....0 (a 个） + 1...1 (b 个）
然后不断把最低位的 0 和他右侧最近的 1 互换，
最地低的 0 到 最右侧之后，倒数第二个 0 进行替换，
替换后把其右侧数字从新从 0 到 1 排列，然后重复上述过程，
直到最大的可能 b 个 1 ＋ a 个 0，用递归好写一点
【在 i******y 的大作中提到】
: 任意给定一个二进制数，比如10111，现在要打印出所有的非零位1的个数和等于k的二
: 进制数。
: 说得比较饶……
: 就比如给你10111，给定K=2，也就是说1的个数和只能等于2
: 那么就要输出：
: 10100， 10010， 10001， 00110， 00101， 00011，大概就是C（4,2）= 6这么多种组
: 合。
: 再比如给定10111，K=3
: 就要输出：
: 10110, 10101， 10011， 00111，一共C（4,3）= 4种.
|
i******y
发帖数: 191 | 3 大概懂你意思了，这样用递归的话，时间复杂度是不是指数级的呢？
跪谢！~~~
【在 b******n 的大作中提到】
: 其实就是 a 个 0， b 个 1 有多少种排列，a b 已知
: 最小的排列是 0....0 (a 个） + 1...1 (b 个）
: 然后不断把最低位的 0 和他右侧最近的 1 互换，
: 最地低的 0 到 最右侧之后，倒数第二个 0 进行替换，
: 替换后把其右侧数字从新从 0 到 1 排列，然后重复上述过程，
: 直到最大的可能 b 个 1 ＋ a 个 0，用递归好写一点
|
b*******e
发帖数: 123 | 4 这个不是等价于m个index(index对应1的位置)中取k个怎么取。c(m,k)指数级别的结果
书目。
怎么样都是指数级别的运算吧？因为至少有个path是print ith number.大牛指正。 |
i******y
发帖数: 191 | 5 我也这么觉得的，等待大牛指正，看有没有什么牛逼算法。
【在 b*******e 的大作中提到】
: 这个不是等价于m个index(index对应1的位置)中取k个怎么取。c(m,k)指数级别的结果
: 书目。
: 怎么样都是指数级别的运算吧？因为至少有个path是print ith number.大牛指正。
|
b******n
发帖数: 4509 | 6 最多 O(n^2)
【在 i******y 的大作中提到】
: 大概懂你意思了，这样用递归的话，时间复杂度是不是指数级的呢？
: 跪谢！~~~
|
b******n
发帖数: 4509 | 7 当然不是，你并没有遍历所有可能
【在 b*******e 的大作中提到】
: 这个不是等价于m个index(index对应1的位置)中取k个怎么取。c(m,k)指数级别的结果
: 书目。
: 怎么样都是指数级别的运算吧？因为至少有个path是print ith number.大牛指正。
|
b******n
发帖数: 4509 | 8
这里要有个排序的步骤，0 右侧的序列排序，变成
1 0 0 1 1 然后继续，这个排序因为只有两个数，所以复杂度是 O(n)
【在 i******y 的大作中提到】
: 我也这么觉得的，等待大牛指正，看有没有什么牛逼算法。
|
n****e
发帖数: 678 | 9 b 个 1只能在原来的数中 1出现的位置排，不是随便排的。
【在 b******n 的大作中提到】
: 其实就是 a 个 0， b 个 1 有多少种排列，a b 已知
: 最小的排列是 0....0 (a 个） + 1...1 (b 个）
: 然后不断把最低位的 0 和他右侧最近的 1 互换，
: 最地低的 0 到 最右侧之后，倒数第二个 0 进行替换，
: 替换后把其右侧数字从新从 0 到 1 排列，然后重复上述过程，
: 直到最大的可能 b 个 1 ＋ a 个 0，用递归好写一点
|
i******y
发帖数: 191 | 10 这个用排列应该没错。
就是忽略掉原来数里面的0，只考虑里面的1
比如10111，里面一共有4个1，当k=2就是在这4个1里面选2个1出来
【在 n****e 的大作中提到】
: b 个 1只能在原来的数中 1出现的位置排，不是随便排的。
|
|
|
n****e
发帖数: 678 | 11 为啥最多是O(n^2)?
我觉得这个题怎么做都是指数级的，顶多算是pseudo polynomial.
【在 b******n 的大作中提到】
: 最多 O(n^2)
|
i******y
发帖数: 191 | 12 发现问题所在了，中间我miss掉了一步判断，不过这样一来我就不会分析时间复杂度了
，感觉不知道还是不是n^2
还是用上面的列子初始化：
0 01 1 1 // 3,4,5
首先从右向左遇到第一个01就把他替换成10：
0 10 1 1 // 2,4,5
同时要保证这个10右边的所有的临近的1都是在最右边的，这一步10后面两个1都在最右
，所以不用动。
算法继续，找到在 0 1 01 1 //2,4,5中的第一个01换成10，得到
0 1 10 1 // 2,3,5
这一步1在最右边，也不动，算法继续
0 1 1 10 // 2,3,4
这一步开始就需要移动位置了，原来是 01 1 1 0 //2,3,4，把01变成10后：
10 1 1 0，注意这个数的10后面有2个1，所以要把这两个1都放到最右边去，也就是说
把 10 1 1 0 => 10 0 1 1 // 1,4,5，这样得到的才是正确的中间步骤。
然后类似，算法继续：
1 0 1 0 1 // 1,3,5
1 0 1 1 0 // 1,3,4
1 10 1 0 => 1 10 0 1 // 1,2,5 （这一步也是要把10后面的1放到最右边去）
1 1 0 1 0 // 1,2,4
1 1 1 0 0 // 1,2,3
这个算法的确把10种可能C（5,3）=C (5,2) = 10全部找到了，但是因为中间多了一项
移位的运算，我就不是很看得懂时间复杂度是多少了（如果不移动的话，感觉应该还是
n^2的），大牛们指教下？？ |
d**********x
发帖数: 4083 | 13 output is O(n chooses k), which is O(n^k).
So the algorithm should at least take O(n^k) time, for k == 2, you do not
need complex algorithm. just a double loop will give you all the answers.
for k > 2, you do not need to optimize -- anyway it is exp complexity.
【在 i******y 的大作中提到】
: 发现问题所在了，中间我miss掉了一步判断，不过这样一来我就不会分析时间复杂度了
: ，感觉不知道还是不是n^2
: 还是用上面的列子初始化：
: 0 01 1 1 // 3,4,5
: 首先从右向左遇到第一个01就把他替换成10：
: 0 10 1 1 // 2,4,5
: 同时要保证这个10右边的所有的临近的1都是在最右边的，这一步10后面两个1都在最右
: ，所以不用动。
: 算法继续，找到在 0 1 01 1 //2,4,5中的第一个01换成10，得到
: 0 1 10 1 // 2,3,5
|
b******n
发帖数: 4509 | 14 上面说过了，这个移位是线性复杂度
所以整个还是 O（n^2)
【在 i******y 的大作中提到】
: 发现问题所在了，中间我miss掉了一步判断，不过这样一来我就不会分析时间复杂度了
: ，感觉不知道还是不是n^2
: 还是用上面的列子初始化：
: 0 01 1 1 // 3,4,5
: 首先从右向左遇到第一个01就把他替换成10：
: 0 10 1 1 // 2,4,5
: 同时要保证这个10右边的所有的临近的1都是在最右边的，这一步10后面两个1都在最右
: ，所以不用动。
: 算法继续，找到在 0 1 01 1 //2,4,5中的第一个01换成10，得到
: 0 1 10 1 // 2,3,5
|
i******y
发帖数: 191 | 15 受教了，看来不管怎么给不同的算法，exp是逃不掉的了
【在 d**********x 的大作中提到】
: output is O(n chooses k), which is O(n^k).
: So the algorithm should at least take O(n^k) time, for k == 2, you do not
: need complex algorithm. just a double loop will give you all the answers.
: for k > 2, you do not need to optimize -- anyway it is exp complexity.
|
d**********x
发帖数: 4083 | 16 errr so i have to fix my statement
it depends on how OP defines the problem -- whether k is fixed :D
【在 i******y 的大作中提到】
: 受教了，看来不管怎么给不同的算法，exp是逃不掉的了
|
i******y
发帖数: 191 | 17 好吧，你好像又说服我了，如果移位是线性的操作，那可能还是n^2.
【在 b******n 的大作中提到】
: 上面说过了，这个移位是线性复杂度
: 所以整个还是 O（n^2)
|
d**********x
发帖数: 4083 | 18 ok... n chooses 3 is n(n-1)(n-2)/6
how can you output n chooses 3 solutions in O(n^2) time?
【在 i******y 的大作中提到】
: 好吧，你好像又说服我了，如果移位是线性的操作，那可能还是n^2.
|
b******n
发帖数: 4509 | 19 哈哈，算法是对的，不过复杂度还是要有点问题，
因为每次排序之后，从新开始，一个 0 可能多次经历替换过程，
所以循环的次数不一定为应该大于 n，所以应该高于 O(n^2)
【在 i******y 的大作中提到】
: 好吧，你好像又说服我了，如果移位是线性的操作，那可能还是n^2.
|
i******y
发帖数: 191 | 20 认真想了下，刚才那个算法，外层就相当于是一个冒泡算法，时间复杂度是n^2，稍微
和冒泡不同的是，他中间多了一个换位的步骤，虽然换位的步骤是线性变换，但估计变
完以后外层的loop也跟着变了，所以估计帅哥你是对的，还是exp级别。
另外我也考虑过组合公式问题，C（5,3）=C（5,2），所以如果按照exp来解释的话，那个
C（n，k）里面的k是不会超过n/2的，因为C（n,k）= C(n,n-k)。
好吧，我错了，不管C（n,k）还是 C(n,n-k)，都是exp……
犯二了
【在 d**********x 的大作中提到】
: ok... n chooses 3 is n(n-1)(n-2)/6
: how can you output n chooses 3 solutions in O(n^2) time?
|
i******y
发帖数: 191 | 21 好吧，我错了，不管C（n,k）还是 C(n,n-k)，都是exp……
犯二了 |
h**6
发帖数: 4160 | 22 C(n,k)是下限，如果限定复杂度为C(n,k)，还是很有难度的。 |
