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

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

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

开发一种方法来表示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

所属标签

可能回答问题的人

  • 天使的炫翼

    17 粉丝531 提问36 回答
  • 富有想象力的人

    3 粉丝0 提问30 回答
  • 学生

    3 粉丝476 提问28 回答
  • o o

    4 粉丝494 提问27 回答

扫码关注云+社区

领取腾讯云代金券