在线性时间生成 Lehmar 代码 - 位集算法
Generating Lehmar code in linear time - bitset algorithm
要生成排列的词典索引，我们首先生成其 Lehmar 代码 - 基本上是阶乘数字系统中的表示。为此，我们取排列的每个元素并减去左边小于它的元素数。你如何找到左边小于排列的特定数字的元素数？如果你简单地扫描所有这些，你可以在线性时间内完成。如果将它们存储在二叉搜索树中，则可以在对数时间内完成。但也有一种方法可以在恒定时间内完成。在博客 here 中，这在 "a linear algorithm" 部分进行了介绍。引用:
让我们再次使用排列 (2 0 1) 来举例说明这个算法。
从长度为 3 的位集开始，初始化为零 (000b)。
排列的第一个元素是2，所以翻转bitset的第2位：001b。如上所述，Lehmer 代码的第一位数字始终与排列的第一位数字相同，在本例中为 2。
- 排列的第二个元素为0，因此设置bitset的第0位：101b。将 bitset 右移 n - k，其中 n 为 3，即排列中的元素数，k 为 0，即排列的第二个元素。 101b >> (3-0) = 000b。计算结果中 1 的个数 (countOnes(000b) = 0)，然后从元素中减去它以获得 Lehmer 数字：0 - 0 = 0.
- 排列的第三个元素为1，因此设置bitset的第1位：111b。右移：111b >> (3-1) = 001b。从元素中减去结果中的个数，得到 Lehmer 数字：1 - countOnes(001b) = 1-1 = 0。
不出所料，Lehmer 代码是 200。
我可以看到这适用于特定的排列，但我完全不知道它为什么有效。
让我们这样看：假设我们处于排列的位置 t。直到现在，位集中的位 i 为 1 当且仅当 i 在当前元素的左侧。当你向右移动 n-k 次时，剩下的是字符串的前 k 位（考虑一直移动 n 次，然后撤消 k 次）所以现在我们有一些 0 和一些 1，每个对应于一个小于当前元素的数字。因此，我们需要做的就是计算结果字符串中的 1。
要生成排列的词典索引，我们首先生成其 Lehmar 代码 - 基本上是阶乘数字系统中的表示。为此，我们取排列的每个元素并减去左边小于它的元素数。你如何找到左边小于排列的特定数字的元素数？如果你简单地扫描所有这些，你可以在线性时间内完成。如果将它们存储在二叉搜索树中，则可以在对数时间内完成。但也有一种方法可以在恒定时间内完成。在博客 here 中，这在 "a linear algorithm" 部分进行了介绍。引用:
让我们再次使用排列 (2 0 1) 来举例说明这个算法。
从长度为 3 的位集开始，初始化为零 (000b)。
排列的第一个元素是2，所以翻转bitset的第2位：001b。如上所述，Lehmer 代码的第一位数字始终与排列的第一位数字相同，在本例中为 2。
- 排列的第二个元素为0，因此设置bitset的第0位：101b。将 bitset 右移 n - k，其中 n 为 3，即排列中的元素数，k 为 0，即排列的第二个元素。 101b >> (3-0) = 000b。计算结果中 1 的个数 (countOnes(000b) = 0)，然后从元素中减去它以获得 Lehmer 数字：0 - 0 = 0.
- 排列的第三个元素为1，因此设置bitset的第1位：111b。右移：111b >> (3-1) = 001b。从元素中减去结果中的个数，得到 Lehmer 数字：1 - countOnes(001b) = 1-1 = 0。 不出所料，Lehmer 代码是 200。
我可以看到这适用于特定的排列，但我完全不知道它为什么有效。
让我们这样看：假设我们处于排列的位置 t。直到现在，位集中的位 i 为 1 当且仅当 i 在当前元素的左侧。当你向右移动 n-k 次时，剩下的是字符串的前 k 位（考虑一直移动 n 次，然后撤消 k 次）所以现在我们有一些 0 和一些 1，每个对应于一个小于当前元素的数字。因此，我们需要做的就是计算结果字符串中的 1。