为了账号安全,请及时绑定邮箱和手机立即绑定

生成长度为n且设置了k位的所有二进制字符串

/ 猿问

生成长度为n且设置了k位的所有二进制字符串

开满天机 2019-09-02 09:17:40

查找包含k位的所有长度为n的二进制字符串的最佳算法是什么?例如,如果n = 4且k = 3,则有......


0111

1011

1101

1110

我需要一个很好的方法来生成这些给定任何n和任何k所以我更喜欢用字符串来完成它。


查看完整描述

3 回答

?
幕布斯7119047

此方法将生成具有正好N'1'位的所有整数。


来自https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation


按字典顺序计算下一位排列

假设我们在整数中有一个N位设置为1的模式,我们希望在字典意义上下一个N 1位的排列。例如,如果N是3和位模式是00010011,下一个模式是00010101,00010110,00011001,00011010,00011100,00100011,等等。以下是计算下一个排列的快速方法。


unsigned int v; // current permutation of bits

unsigned int w; // next permutation of bits


unsigned int t = v | (v - 1); // t gets v's least significant 0 bits set to 1

// Next set to 1 the most significant bit to change,

// set to 0 the least significant ones, and add the necessary 1 bits.

w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));

__builtin_ctz(v)x86 CPU 的GNU C编译器内部函数返回尾随零的数量。如果你使用的是x86的Microsoft编译器,那么内在的就是_BitScanForward。这些都发出bsf 指令,但是其他架构可以使用等价物。如果不是,则考虑使用其中一种方法来计算前面提到的连续零位。这是另一个版本,由于它的除法运算符而往往较慢,但它不需要计算尾随零。


unsigned int t = (v | (v - 1)) + 1;

w = t | ((((t & -t) / (v & -v)) >> 1) - 1);


查看完整回答
反对 回复 2019-09-02
?
慕斯王

蟒蛇


import itertools


def kbits(n, k):

    result = []

    for bits in itertools.combinations(range(n), k):

        s = ['0'] * n

        for bit in bits:

            s[bit] = '1'

        result.append(''.join(s))

    return result


print kbits(4, 3)


Output: ['1110', '1101', '1011', '0111']

说明:


基本上我们需要选择1位的位置。有n个选择k种方式在n个总位中选择k个比特。itertools是一个很好的模块,它为我们这样做。itertools.combinations(range(n),k)将从[0,1,2 ... n-1]中选择k位,然后只需在给定这些位索引的情况下构建字符串。


由于您不使用Python,请在此处查看itertools.combinations的伪代码:


http://docs.python.org/library/itertools.html#itertools.combinations


查看完整回答
反对 回复 2019-09-02
?
慕尼黑的夜晚无繁华

忘掉实现(“用字符串完成”显然是一个实现问题!) - 想想算法,为了Pete的缘故......就像在你的第一个TAG中一样!


你要找的是一组N中的K项的所有组合(指数,0到N-1,设置位)。这显然是递归表达最简单的,例如伪代码:


combinations(K, setN):

  if k > length(setN): return "no combinations possible"

  if k == 0: return "empty combination"

  # combinations INcluding the first item:

  return (first-item-of setN) combined combinations(K-1, all-but-first-of setN)

   union combinations(K-1, all-but-first-of setN)

也就是说,第一个项目是存在还是不存在:如果存在,你有K-1离开(从尾部也称为全冷却),如果不存在,仍然K离开去。


像SML或Haskell这样的模式匹配函数语言可能最能表达这种伪代码(程序性的,就像我的大爱Python一样,实际上可能通过包含过于丰富的功能来过度掩盖问题,例如itertools.combinations,这样可以完成所有艰苦工作你并因此向你隐瞒它!)。


为此,你最熟悉的是什么 - Scheme,SML,Haskell,......?我很乐意为你翻译上面的伪代码。当然,我也可以用Python这样的语言来做 - 但是由于重点是让你理解这个家庭作业的机制,我不会使用过于丰富的功能itertools.combinations,而是递归(和递归 -消除(如果需要)更明显的原语(例如头部,尾部和连接)。但请让我们知道您最熟悉的伪代码语言!(您应该明白,您声明的问题与“获取K项目的所有组合或范围(N)”完全相同,对吧?)。


查看完整回答
反对 回复 2019-09-02

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信