字典序

✍ dations ◷ 2025-09-15 04:06:57 #字典序

字典序是指按照单词首字母顺序在字典中进行排序的方法。

在英文字典中,排列单词的顺序是先按照第一个字母以升序排列(即a、b、c……z 的顺序);如果第一个字母一样,那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长(比如,sigh 和 sight),那么把短者排在前。

通过这种方法,我们可以给本来不相关的单词强行规定出一个顺序。“单词”可以看作是“字母”的字符串,而把这一点推而广之就可以认为是给对应位置元素所属集合分别相同的各个有序多元组规定顺序:下面用形式化的语言说明。

给定两个偏序集和,(,)和(′,′)属于笛卡尔积 × ,则字典序定义为

结果是偏序。如果和是全序, 那么结果也是全序。

上面的定义可以拓展:只要两个元素属于 ××...× 这个笛卡尔积,或者可写成 X=(1, , ..., x) 和 Y=(1, 2, ..., ) 的有序多元组形式,那么两者即可排序——从前往后:

X 和 Y 甚至可以不一样长:只要对应位置的元素所属的集合相同(第一个位置的元素都属于 集合、第二个位置的元素都属于 集合、等等),即可套用上面的做法。如果比到后面发现两者之一的元素先耗尽了,那么可视情况规定短者排在前或在后。

回到英语单词的例子上来。单词可以说是在笛卡尔积 ×××... 这个集合(其中集合 是二十六个英文字母的集合,注意组成笛卡尔积的这些集合不必彼此不同)上的多元组,那么在字典中排列单词的顺序就是这里说的字典序——这也就是“字典序”这个名称的由来。

举例来说,全排列 {1,2,3} 按照字典序的下一个排列分别是 123、132、213、231、312 和 321。如果就数字集合 {1, 2, 3, ..., } 的排列而言,这个集合的全排列本身可以看成是 +1 进制的数,这种情况下,所有排列的字典序等价于所有按照全排列顺序把数字写成的数集合的升序。

相关

  • 范德瓦耳斯方程范德华方程(van der Waals equation)(一译范德瓦耳斯方程),简称范氏方程,是荷兰物理学家范德华于1873年提出的一种实际气体状态方程。范氏方程是对理想气体状态方程的一种改进,特点
  • ATC代码 (V03)A·B·C·D·G·H·QI·J·L·M·N·P·R·S·VATC代码V03(其它各种治疗用药品)是解剖学治疗学及化学分类系统的一个药物分组,这是由世界卫生组织药物统计方法整合中心(The WHO
  • 阿尔孔塔尔阿尔孔塔尔(西班牙语:Alcóntar),是西班牙安达卢西亚自治区阿尔梅里亚省的一个市镇。 总面积94km2, 总人口611人(2001年),人口密度7人/km2。
  • 仁科芳雄仁科芳雄(1890年12月6日-1951年1月10日)是一位日本物理学家,也是日本近代物理的奠基人,被称为“日本物理之父”。他曾是理化学研究所的研究人员,指导过许多著名日本物理学家,包括诺
  • 威廉·特纳·西塞尔顿-戴尔威廉·特纳·西塞尔顿-戴尔(William Turner Thiselton-Dyer,1843年7月28日-1928年12月23日)为英国植物学家。为邱园第三位园长。
  • 太阳制药太阳制药(Sun Pharmaceutical Industries Limited;商业名称:Sun Pharma)是总部位于印度孟买的一家跨国制药公司,主要在印度和美国生产销售各种制药配方和原料药。它成立于1983年,2
  • 沈园沈园位于浙江绍兴越城区东南隅的洋河弄内,始建于宋代,建成之初面积有70多亩,是中国江南著名园林之一。因为沈园最初的主人家姓沈,但具体名字已无从考证,所以称为“沈氏园”。南宋
  • 台9线台9线,又称东部干线,是台湾东部一条南北向的台湾省道,全长453.851千米。北起台北市中正区中山南路忠孝东路口(行政院大门前,台湾公路原点),南迄屏东县枋山乡枫港(衔接台1线往枋寮方向),由北到南纵贯所有东部县市,包括台北的中山南路、罗斯福路,以及北宜公路、苏花公路、花东纵谷公路、南回公路等干线公路,皆是台9线的构成路段,为台湾东部重要公路之一,与西部的台1线大致构成环岛路网。台9甲线 新店-乌来,计划名新北横公路,原本北起新北市新店区青潭,东迄宜兰县宜兰市市区,其中在新店至乌来孝义,即所谓的“新乌公路
  • 朋弟冯棣(1907年-1983年),又名冯止堂,笔名朋弟,出生于大清帝国四川省成都,祖籍北京通县。中国漫画家,曾创作《老夫子》、《阿么林》、《老白薯》、《发财还家》、《上海现形记》等漫画。朋弟青年时期在上海学习美术,相继做过教师、编辑等。1935年至 1937年创作了第一个连续漫画人物“马方人”;1937年至1943年创作的漫画人物“老夫子”、“老白薯”、“阿摩林(吴语上海方言,意为傻瓜)”等在京津一带的报刊上大量刊登。1949年,中华人民共和国建立。1957年朋弟发表了最后的漫画作品《“老白薯”出土》。在反
  • 南岳天台宗南岳天台宗是道教的一个派别,唐朝司马承祯时从茅山宗分化出来。由于该派主要活动在南岳衡山或天台山,因而得名。