字典序

维基百科,自由的百科全书
跳转至: 导航搜索

定义[编辑]

给定两个偏序集AB,(a,b)和(a′,b′)属于笛卡尔集 A × B,则字典序定义为

(a,b) ≤ (a′,b′) 当且仅当 a < a′ 或 (a = a′ 且 bb′).

结果是偏序。如果AB全序, 那么结果也是全序。使用字典序,直观上就如同在字典中排列单词一样排序,按照字母表或数字表里递增顺序的排列次序,即先考虑第一个“字母”,在相同的情况下考虑第二个“字母”,依此类推。假设a=a1a2...an和b1b2...bn是集合{1,2,...,n}的两个排列,字典序下a在b的前面,如果a1<b1或a1=b1且a2<b2,或a1=b1且a2=b2且a3<b3......或a1=b1且a2=b2且......且ak=bk且ak+1<bk+1,或...,依此类推。

例如全排列{1,2,3}按照字典序的下一个排列分别是123, 132, 213, 231, 312, 和321。如果就数字集合{1,2,3,...,n}的排列而言,如果n<=9,那么这个集合的排列本身可以看成是数,这种情况下,排列的字典序等价于这个数字集合的升序。