これは、コーディングの問題というよりはパズルです。特定の制約を満たす 2 進数をいくつ生成できるかを調べる必要があります。入力は
(integer) Len - Number of digits in the binary number
(integer) x
(integer) y
2 進数は、2 進数から隣接する x 桁を取得すると、少なくとも y の 1 が含まれるようにする必要があります。
例えば -
長さ = 6、x = 3、y = 2
0 1 1 0 1 1 - 長さは 6、これから隣接する 3 桁を取ると 2 つの l になります
インタビューでこの C# コーディングの質問がありましたが、これを解決するアルゴリズムがわかりません。コードを探すのではなく (大歓迎ですが)、あらゆる種類のヘルプ、ポインターを歓迎します
LEN = 6、X = 3、Y = 2 の例を使用すると...
X ビットの完全なビット パターン ジェネレーターを構築します。単純なバイナリ カウンターでこれを行うことができます。たとえば、X = 3 の場合、0 から 7 までのカウンターは、長さ 3 の可能なすべてのビット パターンを生成します。
パターンは次のとおりです。
000
001
010
011
100
101
110
111
パターンが構築されるときに隣接要件を確認します。条件を満たしていないパターンはすべて拒否します。基本的に、これは 2 未満の「1」ビット (Y = 2) を含むパターンを拒否することになります。リストは次のように絞り込まれます。
011
101
110
111
プルーニングされたリストの各メンバーに対して、「1」ビットを追加し、最初の X ビットを再テストします。隣接性テストに合格した場合は、新しいパターンを保持します。「0」ビットで同じことを行います。たとえば、このステップは次のように進みます。
1011 <== Keep
1101 <== Keep
1110 <== Keep
1111 <== Keep
0011 <== Reject
0101 <== Reject
0110 <== Keep
0111 <== Keep
どの葉：
1011
1101
1110
1111
0110
0111
枝刈りされたセットが空になるか、メンバーの長さが LEN ビットになるまで、このプロセスを繰り返します。最終的に残ったパターンは次のとおりです。
111011
111101
111110
111111
110110
110111
101101
101110
101111
011011
011101
011110
011111
それらを数えれば完了です。
後続のすべてのパターンは前の手順で検証されているため、反復ごとに最初の X ビットのみをテストする必要があることに注意してください。
入力値が可変であり、実際の出力を確認したかったことを考慮して、再帰アルゴリズムを使用して、特定の長さに対する 0 と 1 のすべての組み合わせを決定しました。
private static void BinaryNumberWithOnes(int n, int dump, int ones, string s = "")
{
if (n == 0)
{
if (BinaryWithoutDumpCountContainsnumberOfOnes(s, dump,ones))
Console.WriteLine(s);
return;
}
BinaryNumberWithOnes(n - 1, dump, ones, s + "0");
BinaryNumberWithOnes(n - 1, dump, ones, s + "1");
}
およびBinaryWithoutDumpCountContainsnumberOfOnesを使用して、2 進数が基準を満たすかどうかを判断します。
private static bool BinaryWithoutDumpCountContainsnumberOfOnes(string binaryNumber, int dump, int ones)
{
int current = 0;
int count = binaryNumber.Length;
while(current +dump < count)
{
var fail = binaryNumber.Remove(current, dump).Replace("0", "").Length < ones;
if (fail)
{
return false;
}
current++;
}
return true;
}
BinaryNumberWithOnes(6, 3, 2) を呼び出すと、一致するすべての 2 進数が出力されます。
010011
011011
011111
100011
100101
100111
101011
101101
101111
110011
110101
110110
110111
111011
111101
111110
111111
ネストされた for ループがそのトリックを行うように思えます。疑似コード (テストされていません)。
value = '0101010111110101010111' // change this line to format you would need
for (i = 0; i < (Len-x); i++) { // loop over value from left to right
kount = 0
for (j = i; j < (i+x); j++) { // count '1' bits in the next 'x' bits
kount += value[j] // add 0 or 1
if kount >= y then return success
}
}
return fail
私のアプローチは、最小数の 1 ですべての 2 進数を取得することから始めることです。これは十分に簡単です。長さ x の 2 進数と y 1 の一意の順列をすべて取得し、それぞれの一意の順列を "Len" 回循環させるだけです。可能なすべての組み合わせでこれらのシードの 0 ビットを反転することにより、基準に適合するすべての 2 進数を反復処理することが保証されます。
from itertools import permutations, cycle, combinations
def uniq(x):
d = {}
for i in x:
d[i]=1
return d.keys()
def findn( l, x, y ):
window = []
for i in xrange(y):
window.append(1)
for i in xrange(x-y):
window.append(0)
perms = uniq(permutations(window))
seeds=[]
for p in perms:
pr = cycle(p)
seeds.append([ pr.next() for i in xrange(l) ]) ###a seed is a binary number fitting the criteria with minimum 1 bits
bin_numbers=[]
for seed in seeds:
if seed in bin_numbers: continue
indexes = [ i for i, x in enumerate(seed) if x == 0] ### get indexes of 0 "bits"
exit = False
for i in xrange(len(indexes)+1):
if( exit ): break
for combo in combinations(indexes, i): ### combinatorically flipping the zero bits in the seed
new_num = seed[:]
for index in combo: new_num[index]+=1
if new_num in bin_numbers:
### if our new binary number has been seen before
### we can break out since we are doing a depth first traversal
exit=True
break
else:
bin_numbers.append(new_num)
print len(bin_numbers)
findn(6,3,2)
このアプローチの成長は間違いなく指数関数的ですが、他の誰かがより複雑なソリューションに到達するのに役立つ場合に備えて、私のアプローチを共有すると思いました...
私の答えはよくわかりませんが、ここに私の見解があります。
長さ = 4、
y=2。
パターンには少なくとも y の 1 が含まれている必要があるため、2 つのパターンを取り出しました。
× 1 1 ×
1×1×
X - ドントケアを表す
最初の式のカウントは 2 1 1 2 =4 になりました
2 番目の式では 1 2 1 2 =4
でも2パターンは共通なのでマイナス2..なので条件を満たすペアは全部で6組。
少なくとも Y 1 ビットを含む長さ X のパターンの数は数えられます。基準を満たす可能性x == yのあるパターンが 1 つだけあることがわかっている場合について説明します。2^x小さい場合は、余分なビットを持つパターンの数と正確にビットを持つyパターンの数を合計する必要があります。1y
choose(n, k) = n! / k! (n - k)!
numPatterns(x, y) {
total = 0
for (int j = x; j >= y; j--)
total += choose(x, j)
return total
}
例えば ：
X = 4, Y = 4 : 1 pattern
X = 4, Y = 3 : 1 + 4 = 5 patterns
X = 4, Y = 2 : 1 + 4 + 6 = 11 patterns
X = 4, Y = 1 : 1 + 4 + 6 + 4 = 15 patterns
X = 4, Y = 0 : 1 + 4 + 6 + 4 + 1 = 16
(all possible patterns have at least 0 1 bits)
基準を満たす長さパターンMの数をとします。さて、その長さパターンはビットのサブセットです。サブパターンには「ウィンドウ」の位置があり、合計パターンが可能です。いずれかのパターンから開始すると、右に a を追加して次のウィンドウに移動すると、既知のパターンの 1 つになることがわかります。問題は、に a を追加し、右にシフトしても、 に有効なパターンを保持できるパターンはいくつあるでしょうか?XYXN(N - x + 1)2^NM1MM0M
ゼロを追加しているので、ゼロからシフトするかM、過剰な1ビットがある場所にすでにいる必要があります。それをひっくり返すために、正確なビットを持ち、. で始まるMパターンがいくつあるかを尋ねることができます。これは、「ビットを持つ長さのパターンの数」と同じで、答え方はわかっています。Y1X-1Y-1
shiftablePatternCount = M - choose(X-1, Y-1)
M の可能性から始めてshiftablePatternCount、右にスライドすると増加します。新しいウィンドウのすべてのパターンは のセットにありM、いくつかのパターンが複製されています。でいっぱいになるまで何回もシフトNし(N - X)、そのたびに でカウントを増やすshiftablePatternCountので、完全な答えは次のようになります。
totalCountOfMatchingPatterns = M + (N - X)*shiftablePatternCount