在不计算其他前缀的情况下获取第i个前缀

Question

我读了这个post，它与我遇到的问题非常接近，但不能概括它。我试图通过使用多个CPU搜索所有路径来解决出差销售人员的问题，我需要的是一种将路径前缀编码为整数并将其分配给每个CPU的方法，这样它就可以知道它应该扫描哪些路径。例如，如果城市的数量是10个，一个可能的3-前缀(假设前缀长度是固定的且已知的)是4-10-3 (有10*9*8个前缀)，那么接收它的CPU将搜索所有以4-10-3开头的路径。因为城市的数量很大，所以我不能计算n！因此我不能使用上面的帖子。

Answer 1

将排列表示为数字的标准表示使用factorial number system中表示的Lehmer codes。其思想是，n个元素的每个排列可以映射到n个数字的序列，第一个数字在0到(n - 1)的范围内，第二个数字在0到(n - 2)的范围内，依此类推。然后，这个数字序列可以表示为阶乘数系统中的单个整数。

我认为应该可以调整这个技巧，使其与排列的前缀一起工作，而不是整个排列。假设您有n个元素，并希望选择其中k个元素的排列。为此，首先计算部分置换的Lehmer码。你得到的不是n个数字的序列，而是k个数字的序列。例如，给定从a b c d e f g提取的部分置换c a d，您的Lehmer代码将如下所示：

• c是a b c d e f g
• a的第二个(索引为零)元素是a b d e f g
• d的第零个(索引为零)元素是b d e f g

的第一个(索引为零)元素

所以Lehmer代码应该是(2, 0, 1)。

一旦您有了这个Lehmer代码，您就可以尝试将其编码为单个整数。为此，您可以使用修改的阶乘数系统编码。具体来说，您可以尝试执行以下操作。如果你有n个元素，并且想要k个元素的排列，那么最后一个元素总共有(n -k+ 1)个可能的选择。倒数第二个元素总共有(n -k+ 2)个可能的选择，倒数第三个元素有(n -k+ 3)个可能的选择，等等。因此，您可以使用Lehmer代码并执行以下操作：

1. 将倒数第二个元素的最后一位数乘以(n -k+1)。
2. 将倒数第三个元素乘以(n -k+ 1)(n -k+ 2) 4...
3. 将第一个元素乘以(n -k+ 1)(n -k+ 2)...(n -1)
4. 将这些值相加。

这将为排列生成一个唯一的整数代码。

例如，我们的Lehmer代码是(2, 0, 1)，n= 7，k= 3。

1+0×(7 -3+ 1) +2×(7 -3+ 2)(7 -3+ 3)

=1+2×(5×6)

=5+2×30

= 61

要反转此过程，您可以获取整数并通过此过程向后运行它，以恢复部分Lehmer代码。为此，首先获取数字并除以(n -k+ 1)(n -k+ 2)...(n - 1)，以取回Lehmer代码的第一位。然后，用(n -k+ 1)(n -k+ 2)...(n - 1)对数字进行mod，以去掉第一个数字。然后，将该数字除以(n -k+ 1)(n -k+ 2)...(n - 2)得到Lehmer码的第二个数字，然后mod除以(n -k+ 1)(n -k+ 2)...(n - 2)得到第二个数字。重复此操作，直到Lehmer代码的所有数字都已重建。

例如，给定前缀61，n= 7，k= 3，我们首先将61除以7×6= 30。这得到2，余数1。因此，Lehmer码的第一个数字是2。通过30修改，我们得到数字1。接下来，我们除以6。这得到0，余数1。因此，第二个数字是0。最后，我们读出剩余的数字，它给出了Lehmer码的最后一位数1。我们已经恢复了Lehmer码(2, 0, 1)，从它我们可以很容易地重建排列。

希望这能有所帮助！

Answer 2

这里最简单的方法是映射前缀，而不是将其视为置换的一部分。不要将前缀映射到0, 10 *9*8-1，而是映射到0,10*10*10-1，所以前缀0,4,5将映射到数字45，前缀4,1,9将映射到数字419 (当然，假设总共有10个城市)。