用k位快速计算b大小的第n个位序列?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (1)
  • 关注 (0)
  • 查看 (35)

开发一种方法来表示k比特集(等于1)的b比特的所有组合。它必须是给定索引的一种方式,可以快速得到二进制序列的相关信息,反之亦然。例如,我认为传统方法是按顺序生成数字,如:对于b = 4和k = 2:

0- 0011

1- 0101

2- 0110

3- 1001

4-1010

5-1100

如果给出序列'1010',我希望能够快速生成数字4作为响应,如果我给出数字4,我希望能够快速生成序列'1010'。然而,我无法想出一个办法来做这些事情,而不必生成所有之前(或之后)的序列。没有必要按顺序生成序列,你可以做0-1001,1-0110,2-0011等等,但是必须在0和(组合b选择k)之间没有重复 - 1并且所有序列都必须被表示。

你会如何处理这个问题?有没有比我使用的算法更好的算法?

提问于
用户回答回答于

pkpnd的建议是正确的,基本上每次处理一位数字,如果是a 1,则通过标准组合方法计算下方存在的选项数量。

nCr()可以由需要O(n^2)存储/时间的表预计算替换。你可以利用另一个属性来减少nCr你需要存储的数量,但是我没有考虑它。你也许可以利用这样的事实,即k每次连续调用之间只递减1,并利用递归公式。

即使有1000个比特,该表格也不应该难以处理。存储答案也不应该太差,因为2 ^ 1000是〜300个数字。如果你的意思是成千上万,那么这将是一个不同的问题。

import math

def nCr(n,r):
    return math.factorial(n) //  math.factorial(r) //  math.factorial(n-r)

def get_index(value):
  b = len(value)
  k = sum(c == '1' for c in value)
  count = 0
  for digit in value:
    b -= 1
    if digit == '1':
      if b >= k:
        count += nCr(b, k)
      k -= 1
  return count

print(get_index('0011')) # 0
print(get_index('0101')) # 1
print(get_index('0110')) # 2
print(get_index('1001')) # 3
print(get_index('1010')) # 4
print(get_index('1100')) # 5

热门问答

腾讯云 TRTC 互动直播 云直播 商业直播区别是什么?

人生的旅途辣鸡前端
推荐
云直播:腾讯云的直播云端处理分发平台 移动直播:腾讯云提供的直播推拉流集成的sdk(iOS、Android、小程序) 互动直播:云直播(云端)+移动直播(终端)+连麦功能 商业直播:基于云直播的直播小程序插件(SaaS腾讯云提供页面模板,PaaS客户自己开发) 商业直播和移动直播...... 展开详请

关于ti-one平台问题?

腾讯智能钛AI开发者

腾讯云 · 智能钛产品团队 (已认证)

腾讯智能钛产品团队官方运营账号。分享产品最新动态,第一时间解答用户疑问。
推荐
您好,感谢您的提问。 TI-ONE平台里的任务是运行在Linux系统上的; 目前TI-ONE工作流任务暂不支持实时查看显存使用情况,notebook任务可在右侧资源栏查看; TI-ONE已上线计费,但目前试运营阶段限时0折。试运营阶段结束,正式开启收费前会提前通知用户定价变动,还...... 展开详请

我刚申请的服务器,缺省给我的是linux,可我要Windows,怎么办?

蒋小爱

腾讯云 · 技术支持 (已认证)

推荐
云服务器提供 不同平台重装:仅支持中国大陆地区(不含中国香港)。 例如,Linux 重装为 Windows,Windows 重装为 Linux 。 参考 重装系统: https://cloud.tencent.com/document/product/213/4933 图片.p...... 展开详请

合作伙伴学院里的学习视频测试题和在线培训系统里的测试题能否提供答案?

骑牛看晨曦love&peace~
推荐

http://tencentcloudxuexi.com 合作伙伴可以登录此平台做练习题,有答案的喔

云服务器不能访问外部网站?

HappyLau谈云计算

腾讯云 · 云计算高级工程师 (已认证)

专注于公有云,私有云解决方案,在kubernetes,openstack,kvm,ceph,linux,shell有丰富的实战经验。
推荐
不能访问外部网站一般是网络和dns的问题,按照如下步骤排查: 1. 确保CVM有外网ip或者NAT转换,使用ping测试下外网的连通性,如果不通请购买弹性公网IP,先申请后购买参考https://cloud.tencent.com/document/product/215/201...... 展开详请

关于Linux DNS服务器设置问题?

mariolu

腾讯 · 后台开发工程师 (已认证)

CDN及云从业者
推荐

CNAME到XX.com,这个XX.COM本身也是需要能解析ip的。CNAME到XX.COM的意义是你能解析到CDN厂商A的域名XX.COM或者CDN厂商B的域名YY.COM。所以需要提供服务的CDN厂商给你他们的域名。这样,DNS查询链路才是完整的。

所属标签

扫码关注云+社区

领取腾讯云代金券