使用正则表达式和布尔逻辑||构造字符串

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的所有序列（不应该太难）的序列，并选择符合你的标准的序列。