0

我正在阅读 Dijkstra 的 EWD 316，我遇到了一个例子。在第 53 页，Dijkstra 给出了以下定义：

考虑由 1、2 和 3 组成的序列，它们仅包含不同的相邻非空子序列对。

他称这样的序列很好。考虑到至少有一个长度为 100 的好序列这一事实，问题是按字母顺序列出所有好的序列，直到并包括第一个长度为 100 的序列。

首先，我认为 Dijkstra 所说的“子序列”是指“子字符串”（我指的是 Wikipedia 上的定义），但这不是真正的问题。据我所知，这个定义是对称的，如果一个序列是好的，那么排列序列中的 1、2 和 3 将产生另一个好的序列。因为定义没有提到具体的数字。然而，Dijkstra 给出了前几个好的序列（按字母顺序），即使序列 21、13、23、31 和 32 不在列表中，例如，12 也在列表中。此外，他的算法删除了试验序列中的最后 3 个。

我很确定我错过了一些微不足道的东西，但我不知道是什么。另外，我不是以英语为母语的人，所以即使您以完全形式/数学符号表达良好的属性，我也会很感激。

ps：我找不到合适的预先存在的标签。

4

1 回答 1

0 
 contain only pairs of different adjoining non-empty subsequences

意味着任何两个相邻的子串都是不同的。我的猜测是，正如您所怀疑的那样，邻接指的是对，而他使用的是子序列这个词而不是子串- 他肯定是指子串，否则3212321就不好了。

所以按字母顺序开始：

1 好，加 1

11不好，去掉后面的3（本例没有），最后一位加1

12 好

121好

1211不好

1212不好

1213好

...

现在，21(and 13, 23, 31...) 在这个列表中吗？21显然是一个“好”的序列。但是21在任何以 开头的字符串之后按字母顺序排列1，因此如果有无数个以 开头的好字符串1，我们将永远不会真正到达21。

想象一个更简单的问题：按字母顺序列出所有自然数。

1
11
111
...

我们永远不会真正到达2. 这并不意味着它不在自然数集中，只是它不在字母列表中的任何有限位置。

于 2013-11-05T16:04:14.063 回答