一个貌似指数级的算法问题求更简单的算法 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

一个貌似指数级的算法问题求更简单的算法

一个貌似指数级的算法问题求更简单的算法# JobHunting - 待字闺中

i*y2013-10-23 07:10

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*n2013-10-23 07:10

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*y2013-10-23 07:10

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*e2013-10-23 07:10

4 楼

这个不是等价于m个index(index对应1的位置)中取k个怎么取。c(m,k)指数级别的结果
书目。
怎么样都是指数级别的运算吧？因为至少有个path是print ith number.大牛指正。

i*y2013-10-23 07:10

5 楼

我也这么觉得的，等待大牛指正，看有没有什么牛逼算法。

【在 b*******e 的大作中提到】

: 这个不是等价于m个index(index对应1的位置)中取k个怎么取。c(m,k)指数级别的结果
: 书目。
: 怎么样都是指数级别的运算吧？因为至少有个path是print ith number.大牛指正。

b*n2013-10-23 07:10

6 楼

最多 O(n^2)

【在 i******y 的大作中提到】

: 大概懂你意思了，这样用递归的话，时间复杂度是不是指数级的呢？
: 跪谢！~~~

b*n2013-10-23 07:10

7 楼

当然不是，你并没有遍历所有可能

【在 b*******e 的大作中提到】

b*n2013-10-23 07:10

8 楼

这里要有个排序的步骤，0 右侧的序列排序，变成
1 0 0 1 1 然后继续，这个排序因为只有两个数，所以复杂度是 O(n)

【在 i******y 的大作中提到】

: 我也这么觉得的，等待大牛指正，看有没有什么牛逼算法。

n*e2013-10-23 07:10

9 楼

b 个 1只能在原来的数中 1出现的位置排，不是随便排的。

【在 b******n 的大作中提到】

i*y2013-10-23 07:10

10 楼

这个用排列应该没错。
就是忽略掉原来数里面的0，只考虑里面的1
比如10111，里面一共有4个1，当k=2就是在这4个1里面选2个1出来

【在 n****e 的大作中提到】

: b 个 1只能在原来的数中 1出现的位置排，不是随便排的。

n*e2013-10-23 07:10

11 楼

为啥最多是O(n^2)?
我觉得这个题怎么做都是指数级的，顶多算是pseudo polynomial.

【在 b******n 的大作中提到】

: 最多 O(n^2)

i*y2013-10-23 07:10

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*x2013-10-23 07:10

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*n2013-10-23 07:10

14 楼

上面说过了，这个移位是线性复杂度
所以整个还是 O（n^2)

【在 i******y 的大作中提到】

i*y2013-10-23 07:10

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*x2013-10-23 07:10

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*y2013-10-23 07:10

17 楼

好吧，你好像又说服我了，如果移位是线性的操作，那可能还是n^2.

【在 b******n 的大作中提到】

: 上面说过了，这个移位是线性复杂度
: 所以整个还是 O（n^2)

d*x2013-10-23 07:10

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*n2013-10-23 07:10

19 楼

哈哈，算法是对的，不过复杂度还是要有点问题，
因为每次排序之后，从新开始，一个 0 可能多次经历替换过程，
所以循环的次数不一定为应该大于 n，所以应该高于 O(n^2)

【在 i******y 的大作中提到】

: 好吧，你好像又说服我了，如果移位是线性的操作，那可能还是n^2.

i*y2013-10-23 07:10

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*y2013-10-23 07:10

21 楼

好吧，我错了，不管C（n,k）还是 C(n,n-k)，都是exp……
犯二了

h*62013-10-23 07:10

22 楼

C(n,k)是下限，如果限定复杂度为C(n,k)，还是很有难度的。