找到所有的n位二进制数有R相邻的数字为1 [英] Finding all n digit binary numbers with r adjacent digits as 1

问题描述

让我举个例子来说。如果n = 4，R = 2，这意味着所有的4位二进制数，且有两个相邻的数字可以是1所以答案是0011 0110 1011 1100 1101

解决方案

  

Q值。我无法找出一个模式或算法。

提示：11可以在位置0,1开始，或2路的两边，该数字必须是零，所以唯一的自由的数字是在剩下的位置，并可以循环使用所有可能的值

例如，如果有n = 10个数字，你要寻找的R = 3相邻，该模式是

  x01110y
 

其中的 X 和是的可循环的所有可能的后缀和prefixes余下的5次免费的数字。请注意，两侧的开头和结尾的零被丢弃，留下六个自由位数的 x0111 和 1110y 的。

下面是使用Python的例子：

 从itertools进口产品

高清根（N，R）：
    生成带有R固定相邻的所有N长序列
    结果=集（）

    固定=元组（[1] * R + [0]）
    对于后缀中的产物（[0,1]，重复= N-R-1）：
        result.add（固定+后缀）

    固定=元组（[0] + [1] * R + [0]）
    REM = N  -  R的 -  2
    对于leadsize范围内（1，REM）：
        在产品数字（[0,1]，重复= REM）：
            result.add（数字[：leadsize] +固定+数字[leadsize：]）

    固定=元组（[0] + [1] * r）的
    为preFIX中的产物（[0,1]，重复= N-R-1）：
        result.add（preFIX +固定）

    返回排序（结果）
 

Let me explain with an example. If n=4 and r=2 that means all 4 digit binary numbers such that two adjacent digits can be 1. so the answer is 0011 0110 1011 1100 1101

解决方案

Q. i am unable to figure out a pattern or an algorithm.

Hint: The 11 can start in position 0, 1, or 2. On either side, the digit must be zero, so the only "free" digits are in the remaining position and can cycle through all possible values.

For example, if there are n=10 digits and you're looking for r=3 adjacent ones, the pattern is

x01110y   

Where x and y can cycle through all possible suffixes and prefixes for the remaining five free digits. Note, on the sides, the leading and trailing zero gets dropped, leaving six free digits in x0111 and 1110y.

Here's an example using Python:

from itertools import product

def gen(n, r):
    'Generate all n-length sequences with r fixed adjacent ones'
    result = set()

    fixed = tuple([1] * r + [0])
    for suffix in product([0,1], repeat=n-r-1):
        result.add(fixed + suffix)

    fixed = tuple([0] + [1] * r + [0])
    rem = n - r - 2
    for leadsize in range(1, rem):
        for digits in product([0,1], repeat=rem):
            result.add(digits[:leadsize] + fixed + digits[leadsize:])

    fixed = tuple([0] + [1] * r)
    for prefix in product([0,1], repeat=n-r-1):
        result.add(prefix + fixed)

    return sorted(result)

这篇关于找到所有的n位二进制数有R相邻的数字为1的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！