使用正则表达式和布尔逻辑构造字符串 ||
如何从由集合 {0,1} 中所有可能的元素组合组成的集合 E* 中构造仅出现一次 111 的字符串？
How do I construct strings with exactly one occurrence of 111 from a set E* consisting of all possible combinations of elements in the set {0,1}?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您可以根据以下步骤生成字符串集：
枚举一些数字及其合法位置：
开始：110
必须有一个，任意位置：111
任意位置：0、010、0110
结束：011
取决于目标字符串的长度（长度应大于3）
条件1：长度=3：{111}
条件2：6>；长度> 3 : (Length-3) = 1x + 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>1长度> 6、你应该考虑两个公式的解：
注释：
length – 3 ：排除 111 的长度
x： 0 出现的次数
y： 010 出现的次数
z： 0110 出现的次数
求所有解 {(x,y,z) | 1x + 3y + 4z = (Length - 3)} ----(1)
对于每个解决方案，您可以生成一个或多个合格的字符串。例如，如果要生成长度为 10 的字符串。(x,y,z) 的一个解是 (0,2,1)，这意味着“010”应该出现两次，而“0110”应该出现一次。基于该解法，可以生成如下字符串：
0: x0 乘以
010: x 2 乘以
0110: x1 乘以
111: x1 乘以（必须有）
求上述元素的排列。
010-0110-010-111 或 111-010-010-0110 …
（长度 - 6）= 1x + 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 个 0 和 1 个 010 组成答案（1,1 ,0)
中间字符串可以是 0 010 或 010 0
那么 ^0010^011 和 110^0100^ 都是合格字符串（111 可以放在任意一个标记为 ^ 的地方）
条件 4：如果 Length > 1。 9、应考虑一个加法公式：
(Length – 9) = 1x + 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'不能保证only-one-111约束。例如，“1”+“11”、“11”+“11”或“1”+“1”+“1”都包含不必要的“111”。为了防止不必要的“111”，我们应该添加“0”来阻止更多相邻的“1”。这会产生三个合格的子字符串“0”、“010”和“0110”。由三个限定子字符串组成的任何组合字符串都将包含零次“111”。
以上三个限定子字符串可以放置在目标字符串中的任何位置，因为它们 100% 确保目标字符串中不会出现额外的“111”。
如果子字符串的位置位于开头或结尾，则只能使用一个“0”来防止“111”。
In start:
10xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
110xxxxxxxxxxxxxxxxxxxxxxxxxxx
In end:
xxxxxxxxxxxxxxxxxxxxxxxxxxx011
xxxxxxxxxxxxxxxxxxxxxxxxxxxx01
这两种情况也能保证不额外有‘111’。
基于上述逻辑。我们可以生成任意长度的目标字符串，其中只有一个“111”。
You can generate the set of strings based on following steps:
Some chucks of numbers and their legal position are enumerated:
Start: 110
Must have one, anywhere: 111
Anywhere: 0, 010, 0110
End: 011
Depend on the length of target string (the length should be bigger than 3)
Condition 1: Length = 3 : {111}
Condition 2: 6 > Length > 3 : (Length-3) = 1x + 3y + 4z
For example, if length is 5: answer is (2,1,0) and (1,0,1)
(2,1,0) -> two '0' and one '010' -> ^0^010^ or ^010^0^ (111 can be placed in any one place marked as ^)
(1,0,1) -> one '0' and one '0110' ...
Condition 3: If 9 > Length > 6, you should consider the solution of two formulas:
Comments:
length – 3 : the length exclude 111
x: the times 0 occurred
y: the times 010 occurred
z: the times 0110 occurred
Finding all solutions {(x,y,z) | 1x + 3y + 4z = (Length - 3)} ----(1)
For each solution, you can generate one or more qualified string. For example, if you want to generate strings of length 10. One solution of (x,y,z) is (0,2,1), that means '010' should occurred twice and '0110' should occurred once. Based on this solution, the following strings can be generated:
0: x0 times
010: x 2 times
0110: x1 times
111: x1 times (must have)
Finding the permutations of elements above.
010-0110-010-111 or 111-010-010-0110 …
(Length - 6) = 1x + 3y + 4z ---(2)
Similar as above case, find all permutations to form an intermediate string.
Finally, for each intermediate string Istr, Istr + 011 or 110 + Istr are both qualified.
For example, (10-6) = 1*0 + 3*0 + 4*1 or = 1*1 + 3*1 + 4*0
The intermediate string can be composed by one '0110' for answer(0,0,1):
Then ^0110^011 and 110^0110^ are qualified strings (111 can be placed in any one place marked as ^)
Or the intermediate string can also be composed by one '0' and one '010' for answer (1,1,0)
The intermediate string can be 0 010 or 010 0
Then ^0010^011 and 110^0100^ are qualified strings (111 can be placed in any one place marked as ^)
Condition 4: If Length > 9, an addition formula should be consider:
(Length – 9) = 1x + 3y + 4z
Similar as above case, find all permutations to form an intermediate string.
Finally, for each intermediate string Istr, 110 + Istr + 011 is qualified.
Explaination:
The logic I use is based on Combinatorial Mathematics. A target string is viewed as a combination of one or more substrings. To fulfill the constraint ('111' appears exactly one time in target string), we should set criteria on substrings. '111' is definitely one substring, and it can only be used one time. Other substrings should prevent to violate the '111'-one-time constraint and also general enough to generate all possible target string.
Except the only-one-111, other substrings should not have more than two adjacent '1'. (Because if other substring have more than two adjacent 1, such as '111', '1111', '11111,' the substring will contain unnecessary '111'). Except the only-one-111, other substrings should not have more than two consecutive '1'. Because if other substring have more than two consecutive 1, such as '111', '1111', '11111,' the substring will contain unnecessary '111' . However, substrings '1' and '11' cannot ensure the only-one-111 constraint. For example, '1'+'11,' '11'+'11' or '1'+'1'+'1' all contain unnecessary '111'. To prevent unnecessary '111,' we should add '0' to stop more adjacent '1'. That results in three qualified substring '0', '010' and '0110'. Any combined string made from three qualified substring will contain zero times of '111'.
Above three qualified substring can be placeed anywhere in the target string, since they 100% ensure no additional '111' in target string.
If the substring's position is in the start or end, they can use only one '0' to prevent '111'.
In start:
10xxxxxxxxxxxxxxxxxxxxxxxxxxxx
110xxxxxxxxxxxxxxxxxxxxxxxxxxx
In end:
xxxxxxxxxxxxxxxxxxxxxxxxxxx011
xxxxxxxxxxxxxxxxxxxxxxxxxxxx01
These two cases can also ensure no additional '111'.
Based on logics mentioned above. We can generate any length of target string with exactly one '111'.
你的问题可能更清楚。
一方面，
"1111"是否包含一次或两次出现"111"？如果是这样，您需要包含
"111"但不包含"1111"或"111.*111"的所有字符串。如果不是，请忽略"1111"的测试。如果我理解正确的话，您正在尝试构造 0 和 1 序列的无限集合的无限子集。如何做到这一点可能取决于您所使用的语言（大多数语言没有表示无限集的方法）。
我最好的猜测是您想要生成所有 0 和 1 序列的序列（这应该不会太难）并选择符合您标准的序列。
Your question could be clearer.
For one thing, does
"1111"contain one occurrence of"111"or two?If so, you want all strings that contain
"111"but do not contain either"1111"or"111.*111". If not, omit the test for"1111".If I understand you correctly, you're trying to construct an infinite subset of the infinite set of sequences of 0s and 1s. How you do that is probably going to depend on the language you're using (most languages don't have a way of representing infinite sets).
My best guess is that you want to generate a sequence of all sequences of 0s and 1s (which shouldn't be too hard) and select the ones that meet your criteria.