本條目存在以下問題,請協助 改善本條目或在 討論頁針對議題發表看法。 |
字典序是指按照单词首字母顺序在字典中进行排序的方法。
概念 编辑
在英文字典中,排列单词的顺序是先按照第一个字母以升序排列(即a、b、c……z 的顺序);如果第一个字母一样,那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长(比如,sigh 和 sight),那么把短者排在前。
通过这种方法,我们可以给本来不相关的单词强行规定出一个顺序。“单词”可以看作是“字母”的字符串,而把这一点推而广之就可以认为是给对应位置元素所属集合分别相同的各个有序多元组规定顺序:下面用形式化的语言说明。
形式定义 编辑
给定两个偏序集A和B,(a,b)和(a′,b′)属于笛卡尔积 A × B,则字典序定义为
- (a,b) ≤ (a′,b′) 当且仅当 a < a′ 或 (a = a′ 且 b ≤ b′).
结果是偏序。如果A和B是全序, 那么结果也是全序。[1][2]
多个集合乘积的场合 编辑
上面的定义可以拓展:只要两个元素属于 A1×A2×...×An 这个笛卡尔积,或者可写成 X=(x1, x2, ..., xn) 和 Y=(y1, y2, ..., yn) 的有序多元组形式,那么两者即可排序——从前往后:
- 如果 x1 和 y1 没有顺序(按照 A1上的偏序,下同):那么 X 和 Y 没有顺序。
- 否则,如果 x1 在 y1 之前,那么 X 在 Y 之前;反之若 y1 在 x1 之前,那么 Y 在 X 之前。
- 否则 x1 和 y1 不分先后。接下来讨论 x2 和 y2、x3 和 y3等等。
X 和 Y 甚至可以不一样长:只要对应位置的元素所属的集合相同(第一个位置的元素都属于 A1 集合、第二个位置的元素都属于 A2 集合、等等),即可套用上面的做法。如果比到后面发现两者之一的元素先耗尽了,那么可视情况规定短者排在前或在后。
回到英语单词的例子上来。单词可以说是在笛卡尔积 A×A×A×... 这个集合(其中集合 A 是二十六个英文字母的集合,注意组成笛卡尔积的这些集合不必彼此不同)上的多元组,那么在字典中排列单词的顺序就是这里说的字典序——这也就是“字典序”这个名称的由来。
举例来说,全排列 {1,2,3} 按照字典序的下一个排列分别是 123、132、213、231、312 和 321。如果就数字集合 {1, 2, 3, ..., n} 的排列而言,这个集合的全排列本身可以看成是 n+1 进制的数,这种情况下,所有排列的字典序等价于所有按照全排列顺序把数字写成的数集合的升序。
参考文献 编辑
字典序, 本條目存在以下問題, 請協助改善本條目或在討論頁針對議題發表看法, 此條目的语调或风格可能不適合百科全書的寫作方式, 2019年5月30日, 請根據指南協助改善这篇条目, 請在讨论页討論問題所在及加以改善, 此條目包含過多行話或專業術語, 可能需要簡化或提出進一步解釋, 2013年10月25日, 請在討論頁中發表對於本議題的看法, 並移除或解釋本條目中的行話, 是指按照单词首字母顺序在字典中进行排序的方法, 目录, 概念, 形式定义, 多个集合乘积的场合, 参考文献概念, 编辑在英文字典中, 排列单词的顺. 本條目存在以下問題 請協助改善本條目或在討論頁針對議題發表看法 此條目的语调或风格可能不適合百科全書的寫作方式 2019年5月30日 請根據指南協助改善这篇条目 請在讨论页討論問題所在及加以改善 此條目包含過多行話或專業術語 可能需要簡化或提出進一步解釋 2013年10月25日 請在討論頁中發表對於本議題的看法 並移除或解釋本條目中的行話 字典序是指按照单词首字母顺序在字典中进行排序的方法 目录 1 概念 2 形式定义 3 多个集合乘积的场合 4 参考文献概念 编辑在英文字典中 排列单词的顺序是先按照第一个字母以升序排列 即a b c z 的顺序 如果第一个字母一样 那么比较第二个 第三个乃至后面的字母 如果比到最后两个单词不一样长 比如 sigh 和 sight 那么把短者排在前 通过这种方法 我们可以给本来不相关的单词强行规定出一个顺序 单词 可以看作是 字母 的字符串 而把这一点推而广之就可以认为是给对应位置元素所属集合分别相同的各个有序多元组规定顺序 下面用形式化的语言说明 形式定义 编辑给定两个偏序集A和B a b 和 a b 属于笛卡尔积 A B 则字典序定义为 a b a b 当且仅当 a lt a 或 a a 且 b b 结果是偏序 如果A和B是全序 那么结果也是全序 1 2 多个集合乘积的场合 编辑上面的定义可以拓展 只要两个元素属于 A1 A2 An 这个笛卡尔积 或者可写成 X x1 x2 xn 和 Y y1 y2 yn 的有序多元组形式 那么两者即可排序 从前往后 如果 x1 和 y1 没有顺序 按照 A1上的偏序 下同 那么 X 和 Y 没有顺序 否则 如果 x1 在 y1 之前 那么 X 在 Y 之前 反之若 y1 在 x1 之前 那么 Y 在 X 之前 否则 x1 和 y1 不分先后 接下来讨论 x2 和 y2 x3 和 y3等等 X 和 Y 甚至可以不一样长 只要对应位置的元素所属的集合相同 第一个位置的元素都属于 A1 集合 第二个位置的元素都属于 A2 集合 等等 即可套用上面的做法 如果比到后面发现两者之一的元素先耗尽了 那么可视情况规定短者排在前或在后 回到英语单词的例子上来 单词可以说是在笛卡尔积 A A A 这个集合 其中集合 A 是二十六个英文字母的集合 注意组成笛卡尔积的这些集合不必彼此不同 上的多元组 那么在字典中排列单词的顺序就是这里说的字典序 这也就是 字典序 这个名称的由来 举例来说 全排列 1 2 3 按照字典序的下一个排列分别是 123 132 213 231 312 和 321 如果就数字集合 1 2 3 n 的排列而言 这个集合的全排列本身可以看成是 n 1 进制的数 这种情况下 所有排列的字典序等价于所有按照全排列顺序把数字写成的数集合的升序 参考文献 编辑 Egbert Harzheim Ordered Sets Springer 2006 88 89 ISBN 978 0 387 24222 4 Franz Baader Tobias Nipkow Term Rewriting and All That Cambridge University Press 1999 18 19 ISBN 978 0 521 77920 3 取自 https zh wikipedia org w index php title 字典序 amp oldid 77356924, 维基百科,wiki,书籍,书籍,图书馆,
文章
,阅读,下载,免费,免费下载,mp3,视频,mp4,3gp, jpg,jpeg,gif,png,图片,音乐,歌曲,电影,书籍,游戏,游戏。