3

例を挙げて説明しましょう。n=4 かつ r=2 の場合、隣接する 2 桁が 1 になるような 4 桁の 2 進数すべてを意味するため、答えは 0011 0110 1011 1100 1101 です。

4

4 に答える 4

3

Q. パターンやアルゴリズムがわかりません。

ヒント: 11 は、0、1、または 2 の位置から開始できます。どちらの側でも、数字は 0 でなければならないため、「空き」数字のみが残りの位置にあり、すべての可能な値を循環できます。

たとえば、n=10 の数字があり、r=3 の隣接する数字を探している場合、パターンは次のようになります。

x01110y

ここで、 xとyは、残りの 5 つの空き桁のすべての可能なサフィックスとプレフィックスを循環できます。両側で、先頭と末尾のゼロが削除され、x0111と1110yに 6 桁の空き桁が残ることに注意してください。

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を1繰り返しm回数、Dを有効な出力を生成するために使用できるすべての可能なサフィックスのセットとします。したがって、ビット文字列S0D0(S の後に 0 ビットが続き、その後にビット文字列Dが続き、その後に 0 ビットが続く) は、アルゴリズムの有効な出力です。また、すべての文字列ror(S0D0, k)は0<=k<=n-m有効な出力です (rorは右回転機能で、右側で消えるビットが左から入ってきます)。これらは にビット文字列S0D0を生成します0D0S。これらのローテーションに加えて、解S0D1と1D0Sはペア ( S、D）。

したがって、このアルゴリズムは、すべての有効なDビット文字列を列挙し、各 ( S , D ) ペアに対して上記のセットを生成するだけです。D部分で複数のm1 を一緒に許可すると、単純なビット列挙になります。そうでない場合は、再帰的な定義です。ここで、D は と を使用した同じアルゴリズムの出力のセットです。n'=n-(m+2)m' is each of {m, m-1, ..., 1}

もちろん、このアルゴリズムはいくつかの重複を生成します。私が考えることができるケースror(S0D0,k)は、パターンの 1 つに一致するときS0E0、S0E1または1E0S. 最初のケースでは、値が大きいほど出力の生成を停止できkます。D=Eジェネレーターがそれらを処理します。他の 2 つのケースを単純にドロップすることもできますが、回転を続ける必要があります。

答えがあることはわかっていますが、アルゴリズムが動作するのを見たかったので、粗いバージョンを実装しました。私が思っていたよりも多くのエッジケースがあることが判明しました。family()関数の最後の 2 つの yield の重複チェックを追加していません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 に答える