计算大小为b的第n个位序列的快速方法，并设置k位？
计算大小为b的第n个位序列的快速方法，并设置k位？
提问于 2018-05-30 08:12:21
我想开发一种方法，能够表示具有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之间不能有重复，并且必须表示所有序列。
您将如何处理此问题？有没有比我用的算法更好的算法？
回答 1
Stack Overflow用户
发布于 2018-05-30 09:10:22
pkpnd的建议是正确的，基本上是一次处理一个数字，如果它是一个1，通过标准组合数学计算它下面存在的选项的数量。
可以用需要O(n^2)存储/时间的表预计算来代替nCr()。您还可以利用另一个属性来减少需要存储的nCr的数量，方法是将absorption property与标准recursive formula结合使用。
即使有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问得好，顺便说一句。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50594667
复制相关文章
相似问题