2

セット{0,1}内の要素のすべての可能な組み合わせで構成されるセットE*から111が1回だけ出現する文字列を作成するにはどうすればよいですか？

4

2 に答える 2

1

次の手順に基づいて一連の文字列を生成できます。

いくつかの数字のチャックとその正当な位置が列挙されています:

開始: 110

どこにでもある必要があります: 111

どこでも: 0, 010, 0110

終了: 011

ターゲット文字列の長さに依存 (長さは 3 より大きくする必要があります)

条件 1: 長さ = 3 : {111}

条件 2: 6 > 長さ > 3 : (長さ-3) = 1x + 3y + 4z

たとえば、長さが 5 の場合: 答えは (2,1,0) と (1,0,1) です。

(2,1,0) -> 2 つの '0' と 1 つの '010' -> ^0^010^ または ^010^0^ (111 は ^ でマークされた任意の場所に配置できます)

(1,0,1) -> 1 つの '0' と 1 つの '0110' ...

条件 3: 9 > 長さ > 6 の場合、次の 2 つの式の解を考慮する必要があります。

コメント:

長さ – 3 : 111 を除く長さ

x: 0 が発生した回数

y: 010 が発生した回数

z: 0110 が発生した時刻

すべての解を見つける {(x,y,z) | 1x + 3y + 4z = (長さ - 3)} ----(1)

ソリューションごとに、1 つ以上の修飾文字列を生成できます。たとえば、長さ 10 の文字列を生成する場合、(x,y,z) の 1 つの解は (0,2,1) であり、これは、'010' が 2 回発生し、'0110' が 1 回発生する必要があることを意味します。このソリューションに基づいて、次の文字列を生成できます。

0: x0 回

010:×2回

0110: x1回

111：×1回（必須）

上記の要素の順列を見つける。010-0110-010-111 または 111-010-010-0110 …</p>

(長さ - 6) = 1x + 3y + 4z ---(2) 上記の場合と同様に、すべての順列を見つけて中間文字列を形成します。最後に、中間文字列 Istr ごとに、Istr + 011 または 110 + Istr の両方が修飾されます。

たとえば、(10-6) = 1*0 + 3*0 + 4*1 または = 1*1 + 3*1 + 4*0

中間文字列は、answer(0,0,1) に対して 1 つの '0110' で構成できます: ^0110^011 と 110^0110^ は修飾文字列です (111 は ^ としてマークされた任意の場所に配置できます)。

または、中間文字列を 1 つの '0' と 1 つの '010' で構成して、回答 (1,1,0) にすることもできます。

中間文字列は 0 010 または 010 0 にすることができます ^0010^011 および 110^0100^ は修飾文字列です (111 は ^ としてマークされた任意の場所に配置できます)

条件 4: 長さ > 9 の場合、加算式を考慮する必要があります。

(長さ – 9) = 1x + 3y + 4z

上記の場合と同様に、すべての順列を見つけて中間文字列を形成します。最後に、中間文字列 Istr ごとに、110 + Istr + 011 が修飾されます。

説明:

私が使用するロジックは、組み合わせ数学に基づいています。ターゲット文字列は、1 つ以上の部分文字列の組み合わせとして表示されます。制約 ('111' はターゲット文字列に 1 回だけ出現する) を満たすには、部分文字列に基準を設定する必要があります。'111' は間違いなく 1 つの部分文字列であり、1 回しか使用できません。他の部分文字列は、'111' の 1 回限りの制約に違反することを防ぎ、可能なすべてのターゲット文字列を生成するのに十分一般的である必要があります。

only-one-111 を除いて、他の部分文字列には 2 つ以上の隣接する '1' があってはなりません。('111'、'1111'、'11111' のように、他の部分文字列に 2 つ以上の隣接する 1 がある場合、部分文字列には不要な '111' が含まれるため)。only-one-111 を除いて、他の部分文字列には 2 つ以上連続する「1」があってはなりません。'111'、'1111'、'11111' など、他の部分文字列に 1 が 2 つ以上連続する場合、部分文字列には不要な '111' が含まれます。ただし、部分文字列 '1' および '11' は、111 個のみの制約を保証できません。たとえば、'1'+'11'、'11'+'11' または '1'+'1'+'1' にはすべて不要な '111' が含まれています。不要な「111」を避けるために、「0」を追加する必要があります さらに隣接する '1' を停止します。その結果、修飾された 3 つの部分文字列 '0'、'010'、および '0110' が生成されます。修飾された 3 つの部分文字列から作成された結合文字列には、'111' のゼロ回が含まれます。

上記の 3 つの修飾部分文字列は、ターゲット文字列に「111」が追加されないことを 100% 保証するため、ターゲット文字列のどこにでも配置できます。

部分文字列の位置が先頭または末尾にある場合、「111」を防ぐために「0」を 1 つだけ使用できます。

はじめに:

10xxxxxxxxxxxxxxxxxxxxxxxxxxx

110xxxxxxxxxxxxxxxxxxxxxxxxxxx

最後に：

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx011

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx01

これらの 2 つのケースでは、「111」が追加されないようにすることもできます。

上記のロジックに基づいています。'111' を 1 つだけ使用して、任意の長さのターゲット文字列を生成できます。

于 2011-09-24T03:39:37.253 に答える
0

あなたの質問はより明確になる可能性があります。

1 つには、 1 つまたは 2"1111"つのオカレンスが含まれています"111"か?

その場合、またはを含む"111"が含まないすべての文字列が必要です。そうでない場合は、 のテストを省略します。"1111""111.*111""1111"

私の理解が正しければ、あなたは 0 と 1 のシーケンスの無限セットの無限サブセットを構築しようとしています。それをどのように行うかは、おそらく使用している言語によって異なります (ほとんどの言語には、無限集合を表す方法がありません)。

私の最善の推測は、0 と 1 のすべてのシーケンスのシーケンスを生成し (これはそれほど難しくないはずです)、基準を満たすものを選択することです。

于 2011-09-24T05:12:51.383 に答える