2

如何从包含集合 {0,1} 中元素的所有可能组合的集合 E* 中构造恰好出现一次 111 的字符串？

4

2 回答 2

1

您可以根据以下步骤生成字符串集：

列举了一些数字及其法律地位：

开始： 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^ or ^010^0^ (111可以放在任何一个标记为^的地方)

(1,0,1) -> 一个 '0' 和一个 '0110' ...

条件 3：如果 9 > Length > 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 …</p>

(Length - 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可以放在任何一个标记为^的地方）

或者中间字符串也可以由一个'0'和一个'010'组成答案（1,1,0）

中间字符串可以是 0 010 或者 010 0 那么^0010^011和110^0100^是合格的字符串（111可以放在任何一个标记为^的地方）

条件 4：如果 Length > 9，则应考虑加法公式：

（长度 - 9）= 1x + 3y + 4z

与上述情况类似，找到所有排列以形成中间字符串。最后，对于每个中间字符串 Istr，110 + Istr + 011 是合格的。

解释：

我使用的逻辑基于组合数学。目标字符串被视为一个或多个子字符串的组合。为了满足约束（“111”在目标字符串中恰好出现一次），我们应该对子字符串设置标准。'111' 绝对是一个子串，而且只能使用一次。其他子字符串应防止违反“111”一次性约束，并且足够通用以生成所有可能的目标字符串。

除了 only-one-111 之外，其他子串不应有超过两个相邻的 '1'。（因为如果其他子串有两个以上相邻的1，例如'111'、'1111'、'11111'，则子串会包含不必要的'111'）。除了 only-one-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'。

在开始：

10xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

110xxxxxxxxxxxxxxxxxxxxxxxxxxx

最后：

xxxxxxxxxxxxxxxxxxxxxxxxxxx011

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx01

这两种情况也可以确保没有额外的“111”。

基于上述逻辑。我们可以生成任意长度的目标字符串，其中恰好有一个 '111'。

于 2011-09-24T03:39:37.253 回答
0

你的问题可能更清楚。

一方面，确实"1111"包含一次"111"或两次？

如果是这样，您需要所有包含"111"但不包含"1111"or的字符串"111.*111"。如果不是，请省略对 的测试"1111"。

如果我对您的理解正确，您正在尝试构建 0 和 1 的无限序列的无限子集。您如何做到这一点可能取决于您使用的语言（大多数语言没有表示无限集的方法）。

我最好的猜测是，您想要生成所有 0 和 1 序列的序列（这应该不会太难）并选择符合您标准的序列。

于 2011-09-24T05:12:51.383 回答