Browsed by
Tag: 排列组合

字典序:生成下一个排列

字典序:生成下一个排列

用字典序生成排列,一个排列若按字典序,可以设计如下的树,例如N=4,根结点有4个子树,按顺序将这四个树的结点值排好。每个子树又有3个子树,其结点的值是父结点所不含有的那些值。直到将N层建好,则依次就是字典序的排列。 按照字典序的规则,已知一个N的排列 \( p_1,p_2,…p_N \)…

Read More Read More

序数法:一种排列的生成算法

序数法:一种排列的生成算法

一个\([ 0, n!-1] \)当中的整数m,先将其转化为唯一确定的长度 n-1 的序数\( (a_{n-1},…a_1) \),再将这个序数转化为长度为n的一个排列。 下边详细介绍此方法和理论: 首先 类似地, 将上式代入最后一项,并运用多次则得: 那么0到\( n!-1 \)的整数…

Read More Read More

第k个排列数:康托展开

第k个排列数:康托展开

序列中各个元素都不相同,将这个序列进行全排列,并且将所有排列从小到大排序。现在给定一个序列,确定这是第几个排列。以及它的逆问题:确定第k个排列是什么。这可用Cantor展开以及逆Cantor展开。 康托展开是一个全排列到一个自然数的双射,常用于构建hash表时的空间压缩。 例如,N=4的不重复序列\…

Read More Read More