3

アダマール行列のいくつかのバリアントで遊んでいます。これらの要件を満たすすべての nビットのバイナリ文字列を生成したい:

  1. nは 4 の倍数であると仮定できます。
  2. 最初の文字列は 0 nです。
    → すべて 0 の文字列。
  3. 残りの文字列はアルファベット順にソートされます。
    → 0 は 1 の前に来ます。
  4. 2 つの異なるnビット文字列ごとに、ハミング距離 n/2があります。
    → 2 つの異なるnビット文字列は、正確に n/2 の位置で一致し、正確にn/2の位置で一致しません。
  5. 上記の条件により、最初の文字列を除くすべての文字列は、同じ数の 0 と 1 を持つ必要があります。
    → 最初の文字列以外のすべての文字列には、n/2 個の 1 と n/2 個のゼロが含まれている必要があります。
  6. (更新) すべてのnビット文字列は で始まります0。

たとえば、これはn=4の場合に必要なリストです。

0000
0011
0101
0110

2 つの異なる行ごとにハミング距離n/2 = 4/2 = 2があり、リストが他のすべての要件も満たしていることが簡単にわかります。

そのような文字列をすべて生成したいことに注意してください。私のアルゴリズムは、終了する前に0000, 0011, の3 つの文字列を出力するだけかもしれません。0101このリストは上記のすべての要件を満たしていますが、要件を満たしていません0110。

  1. そのようなセットを生成する良い方法は何でしょうか?
    Python 疑似コードが推奨されますが、高レベルの説明であれば何でもかまいません。
  2. 特定のnに対するそのような文字列の最大数は? たとえば、n=4の場合、そのような文字列の最大数はたまたま 4 になります。この上限に対して閉じた形式のソリューションがあるかどうか疑問に思っています。

ありがとう。

4

1 に答える 1

0

質問1に答えるには、

nゼロの文字列( it と呼びましょうs0) とゼロの文字列の後に1n/2が続く( it と呼びます)から始めて、次の順列を生成します ( it と呼びます)。n/2s1p

scan string from right to left
replace first occurrence of "01" with "10"
(unless the first occurrence is at the string start)
move all "1"'s that are on the right of the "01" to the string end
return replaced string

順列生成順序を使用して、セットに追加された順列の記録を保持します。xor現在セット内の各数値でingに設定されているビット数pが n/2の場合p、リストに追加します。xorそれ以外の場合、 ingpで設定されたビット数s1が n/2 であり、記録されていない場合は、;pで新しいセット検索を開始します。xor テストの追加条件としてのみ使用されます (一次検索ではすべての順列が確認されるため、このセットは追加のセットを生成する必要はありません)。次の順列を生成するために使用します。s0s1pp

于 2013-09-19T11:07:26.817 に答える