使用正則表達式和布爾邏輯||構造字符串

Question

如何構造一個集合E *中出現111的恰好一次出現的字符串，集合{0,1}中所有可能的元素組合？

Answer 1

您可以生成一組基於以下步驟字符串：

數的幾個夾頭及其法律地位列舉：

---

開始：110

必須有一個，任何地方：111

任意位置：0,010,0110

結束：011

---

依靠目標串的長度（長度應大於3）

條件1：長度= 3：{111}

---

條件2 ：6>長度> 3：（長度-3）= 1×+ 3Y + 4Z

---

例如，如果長度爲5：答案是（2,1,0）和（ 1,0,1）

（2,1,0）→兩個'0'和一個'010' - >^0^010 ^或^ 010^0 ^（111可以放在任何一個地方標記爲^）

（1,0,1） - >一個 '0' 和一個 '0110' ......

條件3：如果9>長度> 6，你應該考慮的兩個解決方案公式：

---

評論：

長度 - 3：長度排除111

X：時代0發生

Y：該次發生010

Z：該次發生0110

---

找到所有的解決方案{（X，Y，Z）| 1x + 3y + 4z =（長度-3）} ----（1）

對於每個解決方案，您可以生成一個或多個限定字符串。例如，如果要生成長度爲10的字符串。（x，y，z）的一個解是（0,2,1），這意味着'010'應該發生兩次，'0110'應該發生一次。根據該解決方案，可以產生以下字符串：

---

0：X0倍

010：×2次

0110：X1倍

111：X1倍（必須有）

---

查找上述元素的排列。 010-0110-010-111或111-010-010-0110 ...

（長度 - 6）= 1×+ 3Y + 4Z ---（2） 如上情況相類似，發現所有的排列，以形成一中間字符串。 最後，對於每個中間字符串Istr，Istr + 011或110 + Istr都是合格的。

例如，（10-6）= 1 * 0 + 3 * 0 + 4 * 1或= 1 * 1 + 3 * 1 + 4 * 0

中間串可以由一個'組成0110' 的回答（0,0,1）： 然後^ 0110^011和110^0110 ^是合格的字符串（111可以被放置在標記爲^任何一個地方）

或中間串也可以是（1,1,0）

中間字符串可以是0 010或010 0 然後^ 0010^011和110^0100 ^是合格的字符串（111可以放在任何o中NE地方標記爲^）

條件4：如果長度> 9，加法公式應考慮：

---

（長度 - 9）= 1×+ 3Y + 4Z

類似如上情況下，找到所有排列組成一箇中間字符串。 最後，對於每個中間字符串Istr，110 + Istr + 011是合格的。

---

闡釋：

我使用的邏輯是基於組合數學。目標字符串被視爲一個或多個子字符串的組合。爲了完成約束（'111'在目標字符串中只出現一次），我們應該在子字符串上設置標準。 '111'絕對是一個子字符串，只能使用一次。其他子串應該防止違反'111'一次性約束，並且還足以產生所有可能的目標串。

除了唯一一個111，其他子串不應該有兩個以上相鄰的'1'。 （因爲如果其他子字符串具有多於兩個相鄰的1，例如'111'，'1111'，'11111'，則子字符串將包含不必要的'111'）。除了唯一的-111之外，其他子串不應該有兩個以上連續的'1'。因爲如果其他子串具有多於兩個連續的1，如'111'，'1111'，'11111'，則子串將包含不必要的'111'。但是，子串「1」和「11」不能確保唯一一個-111約束。例如，'1'+'11'，'11'+'11'或'1'+'1'+'1'都包含不必要的'111'。爲了防止不必要的'111'，我們應該加'0'來停止更多的相鄰'1'。這導致三個限定的子字符串「0」，「010」和「0110」。由三個限定子字符串組成的任何組合字符串將包含零次'111'。

以上三個限定的子字符串可以放置在目標字符串的任何位置，因爲它們100％確保目標字符串中沒有附加的'111'。

如果子串的位置在開始或結束，它們只能使用一個'0'來阻止'11​​1'。

在開始：

10xxxxxxxxxxxxxxxxxxxxxxxxxxxx

110xxxxxxxxxxxxxxxxxxxxxxxxxxx

在端：

xxxxxxxxxxxxxxxxxxxxxxxxxxx011

xxxxxxxxxxxxxxxxxxxxxxxxxxxx01

帖兩種情況也可以確保沒有額外的'111'。

基於上面提到的邏輯。我們可以用一個'111'生成任意長度的目標字符串。

Answer 2

你的問題可能會更清楚。

一方面，"1111"是否包含"111"或兩個？

如果是這樣，您需要包含"111"但不包含"1111"或"111.*111"的所有字符串。如果不是，則省略"1111"的測試。

如果我正確理解你，你試圖構造0和1的無限序列集的無限子集。如何做到這一點可能取決於你使用的語言（大多數語言沒有表示無限集合的方式）。

我最好的猜測是你想要生成一個0和1的所有序列（不應該太難）的序列，並選擇符合你的標準的序列。