3

让我用一个例子来解释。如果 n=4 且 r=2 表示所有 4 位二进制数，因此相邻的两个数字可以是 1。所以答案是 0011 0110 1011 1100 1101

4

4 回答 4

3

问：我无法找出模式或算法。

提示：11 可以从位置 0、1 或 2 开始。在任一侧，数字必须为零，因此唯一的“空闲”数字位于剩余位置，并且可以循环遍历所有可能的值。

例如，如果有 n=10 个数字并且您正在寻找 r=3 个相邻的数字，则模式是

x01110y

其中x和y可以循环遍历剩余五个自由数字的所有可能的后缀和前缀。请注意，在两侧，前导零和尾随零被丢弃，在x0111和1110y中留下六个空闲数字。

这是一个使用 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)
于 2012-05-09T05:45:53.703 回答
1

我将从简化问题开始。一旦你为最简单的情况找到了解决方案，就对其进行概括，然后尝试对其进行优化。

首先设计一个算法，找出给定数字是否有“r”个相邻的 1。一旦你有了它，蛮力的方法是遍历所有带有“n”位的数字，用你刚刚开发的算法检查每个数字。

现在，您可以寻找优化它。例如：如果您知道“r”是偶数还是奇数，您可以减少要查看的数字集。KNR 给出的计数 1 的算法是设置位数的顺序。因此，您排除了一半复杂度低于实际逐点比较的情况。也可能有更好的方法来减少这种情况。

于 2012-05-09T05:30:49.067 回答
1

非常简单的递归解决方案的有趣问题。德尔福。

  procedure GenerateNLengthWithROnesTogether(s: string;
    N, R, Len, OnesInRow: Integer; HasPatternAlready: Boolean);
  begin
    if Len = N then
      Output(s)
    else
    begin
      HasPatternAlready := HasPatternAlready or (OnesInRow >= R);
      if HasPatternAlready or (N - Len > R) //there is chance to make pattern}
       then
        GenerateNLengthWithROnesTogether('0' + s, N, R, Len + 1, 0, HasPatternAlready);
      if (not HasPatternAlready) or (OnesInRow < R - 1) //only one pattern allowed
      then
        GenerateNLengthWithROnesTogether('1' + s, N, R, Len + 1, OnesInRow + 1, HasPatternAlready);
    end;
  end;

begin
  GenerateNLengthWithROnesTogether('', 5, 2, 0, 0, False);
end;

program output:
N=5,R=2
11000  01100 11010  00110
10110  11001 01101  00011
10011  01011

N=7, R=3
1110000 0111000 1110100 0011100
1011100 1110010 0111010 1110110
0001110 1001110 0101110 1101110
1110001 0111001 1110101 0011101
1011101 1110011 0111011 0000111
1000111 0100111 1100111 0010111
1010111 0110111
于 2012-05-09T07:10:34.323 回答
0

正如我在上面的评论中所说，我仍然不清楚输出集的全部限制。但是，可以改进下面的算法以涵盖您的最终情况。

在我描述算法之前，有一个观察结果：让S重复次数，1D是我们可以用来生成有效输出的所有可能后缀的集合。因此，位串（S 后跟 0 位，位串D后跟 0 位）是算法的有效输出。此外，所有字符串都是有效输出（是右转函数，右侧消失的位从左侧进入）。这些将生成位串到. 除了这些旋转之外，解决方案和是可以由该对生成的有效位串 ( SmS0D0ror(S0D0, k)0<=k<=n-mrorS0D00D0SS0D11D0S, D )。

因此，该算法只是简单地枚举所有有效的D位字符串，并为每个 ( S , D ) 对生成上述集合。如果在D部分允许多个m1 一起使用，则为简单的位枚举。如果不是，它是一个递归定义，其中 D 是与和相同算法的输出集。n'=n-(m+2)m' is each of {m, m-1, ..., 1}

当然，这个算法会产生一些重复。我能想到的情况是ror(S0D0,k)匹配其中一种模式S0E0，S0E1或1E0S。对于第一种情况，您可以停止为更大的k值生成更多输出。D=E生成器会处理这些。您也可以简单地删除其他两种情况，但您需要继续旋转。

我知道有答案，但我想看看算法在起作用，所以我实现了一个粗略的版本。事实证明，边缘情况比我意识到的要多。我没有为family()函数的最后两个产量添加重复检查，这会导致输出重复11011，但其中大部分都被消除了。

def ror(str, n):
    return str[-n:]+str[:-n]

def family(s, d, r):
    root = s + '0' + d + '0'
    yield root  # root is always a solution
    for i in range(1, len(d)+3):
        sol=ror(root, i)
        if sol[:r]==s and sol[r]=='0' and sol[-1]=='0':
            break
        yield sol
    if d[-r:]!=s: # Make sure output is valid
        yield s + '0' + d + '1'
    if d[:r]!=s:  # Make sure output is valid (todo: duplicate check)
        yield '1' + d + '0' + s

def generate(n, r):
    s="1"*r
    if r==0: # no 1's allowed
        yield '0'*n
    elif n==r: # only one combination
        yield s
    elif n==r+1: # two cases. Cannot use family() for this
        yield s+'0'
        yield '0'+s
    else:
        # generate all sub-problem outputs
        for rr in range(r+1):
            if n-r-2>=rr:
                for d in generate(n-r-2, rr):
                    for sol in family(s, d, r):
                        yield sol

您可以将其用作[s for s in generate(6,2)]，或在循环中用作

for s in generate(6,3):
    print(s)
于 2012-05-09T14:55:42.623 回答