在不计算其他排列的情况下查找第 n 个排列

php algorithm math permutation

2022-08-30 10:58:00

给定一个表示排列原子的N个元素数组，是否存在这样的算法：

function getNthPermutation( $atoms, $permutation_index, $size )

其中是元素数组，是排列的索引，是排列的大小。$atoms$permutation_index$size

例如：

$atoms = array( 'A', 'B', 'C' );
// getting third permutation of 2 elements
$perm = getNthPermutation( $atoms, 3, 2 );

echo implode( ', ', $perm )."\n";

将打印：

B, A

无需计算每个排列，直到$permutation_index ？

我听说过一些关于阶乘排列的东西，但是我发现的每个实现都给出了具有相同V大小的排列，这不是我的情况。

谢谢。

答案 1

正如RickyBobby所说，在考虑排列的词典顺序时，你应该使用阶乘分解来发挥自己的优势。

从实际的角度来看，这就是我的看法：

执行某种欧几里得除法，除了你用阶乘数来做，从、开始，依此类推。(n-1)!(n-2)!
将商保留在数组中。第 -th 个商应为介于和（包含）之间的数字，其中从到。i0n-i-1i0n-1
此数组是您的排列。问题是每个商都不关心以前的值，所以你需要调整它们。更明确地说，您需要将每个值递增到与先前值较低或等于的值一样多次。

下面的C代码应该可以让您了解它是如何工作的（是条目的数量，并且是排列的索引）：ni

/**
 * @param n The number of entries
 * @param i The index of the permutation
 */
void ithPermutation(const int n, int i)
{
   int j, k = 0;
   int *fact = (int *)calloc(n, sizeof(int));
   int *perm = (int *)calloc(n, sizeof(int));

   // compute factorial numbers
   fact[k] = 1;
   while (++k < n)
      fact[k] = fact[k - 1] * k;

   // compute factorial code
   for (k = 0; k < n; ++k)
   {
      perm[k] = i / fact[n - 1 - k];
      i = i % fact[n - 1 - k];
   }

   // readjust values to obtain the permutation
   // start from the end and check if preceding values are lower
   for (k = n - 1; k > 0; --k)
      for (j = k - 1; j >= 0; --j)
         if (perm[j] <= perm[k])
            perm[k]++;

   // print permutation
   for (k = 0; k < n; ++k)
      printf("%d ", perm[k]);
   printf("\n");

   free(fact);
   free(perm);
}

例如，如预期的那样，打印十个元素的最后排列：ithPermutation(10, 3628799)

9 8 7 6 5 4 3 2 1 0

答案 2

下面是一个允许选择排列大小的解决方案。例如，除了能够生成10个元素的所有排列之外，它还可以在10个元素之间生成对的排列。此外，它还会置换任意对象的列表，而不仅仅是整数。

function nth_permutation($atoms, $index, $size) {
    for ($i = 0; $i < $size; $i++) {
        $item = $index % count($atoms);
        $index = floor($index / count($atoms));
        $result[] = $atoms[$item];
        array_splice($atoms, $item, 1);
    }
    return $result;
}

用法示例：

for ($i = 0; $i < 6; $i++) {
    print_r(nth_permutation(['A', 'B', 'C'], $i, 2));
}
// => AB, BA, CA, AC, BC, CB

它是如何工作的？

这背后有一个非常有趣的想法。让我们以列表为例。我们可以通过从中绘制元素来构造排列，就像从一副纸牌中绘制元素一样。最初，我们可以绘制四个元素之一。然后是剩下的三个元素中的一个，依此类推，直到最后我们一无所有。A, B, C, D

Decision tree for permutations of 4 elements

以下是一个可能的选择序列。从顶部开始，我们走第三条路，然后是第一条路，第二条路，最后是第一条路。这就是我们的排列#13。

想想看，给定这个选择序列，你如何通过算法得到数字13。然后反转你的算法，这就是你如何从整数重建序列。

让我们尝试找到一种通用方案，用于将一系列选择打包成一个没有冗余的整数，然后将其解压缩回去。

一个有趣的方案称为十进制数系统。“27”可以被认为是从10中选择路径#2，然后在10中选择路径#7。

Decision three for number 27 in decimal

但每个数字只能编码10个备选方案中的选项。具有固定基数的其他系统（如二进制和十六进制）也只能对固定数量的备选项中的选择序列进行编码。我们想要一个具有可变基数的系统，有点像时间单位，“14：05：29”是从24开始的小时14，从60开始的分钟5，从60开始的第二个29。

如果我们采用通用的数字到字符串和字符串到数字的函数，并欺骗它们使用混合基数，该怎么办？它们不是像 parseInt（'beef'， 16）和（48879）.toString（16）那样取单个基数，而是每个数字取一个基数。

function pack(digits, radixes) {
    var n = 0;
    for (var i = 0; i < digits.length; i++) {
        n = n * radixes[i] + digits[i];
    }
    return n;
}

function unpack(n, radixes) {
    var digits = [];
    for (var i = radixes.length - 1; i >= 0; i--) {
        digits.unshift(n % radixes[i]);
        n = Math.floor(n / radixes[i]);
    }
    return digits;
}

这甚至有效吗？

// Decimal system
pack([4, 2], [10, 10]); // => 42

// Binary system
pack([1, 0, 1, 0, 1, 0], [2, 2, 2, 2, 2, 2]); // => 42

// Factorial system
pack([1, 3, 0, 0, 0], [5, 4, 3, 2, 1]); // => 42

现在倒过来：

unpack(42, [10, 10]); // => [4, 2]

unpack(42, [5, 4, 3, 2, 1]); // => [1, 3, 0, 0, 0]

这真是太美了。现在，让我们将此参数化数字系统应用于排列问题。我们将考虑的长度 2 排列。它们的总数是多少？让我们看看：首先我们绘制4个项目中的一个，然后绘制其余3个项目中的一个，这就是绘制2个项目的方法。这 12 种方式可以打包成整数 [0..11]。所以，让我们假装我们已经打包了它们，并尝试解压缩：A, B, C, D4 * 3 = 12

for (var i = 0; i < 12; i++) {
    console.log(unpack(i, [4, 3]));
}

// [0, 0], [0, 1], [0, 2],
// [1, 0], [1, 1], [1, 2],
// [2, 0], [2, 1], [2, 2],
// [3, 0], [3, 1], [3, 2]

这些数字表示选择，而不是原始数组中的索引。[0， 0] 并不意味着采取，它意味着从（即A）中获取项目#0，然后从其余列表（即B）中获取项目#0。得到的排列是。A, AA, B, C, DB, C, DA, B

另一个例子：[3，2]意味着从（即D）中获取项目#3，然后从其余列表（即C）中获取项目#2。得到的排列是。A, B, C, DA, B, CD, C

此映射称为 Lehmer 代码。让我们将所有这些 Lehmer 代码映射到排列：

AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC

这正是我们所需要的。但是，如果您查看该函数，您会注意到它从右到左生成数字（以反转的操作）。从 3 中选择在从 4 中选择之前被解压缩。这很不幸，因为我们希望先从 4 个元素中进行选择，然后再从 3 个元素中进行选择。如果不能这样做，我们必须首先计算Lehmer代码，将其累积到一个临时数组中，然后将其应用于项目数组以计算实际的排列。unpackpack

但是，如果我们不关心词典顺序，我们可以假装我们想要从3个元素中进行选择，然后再从4个元素中进行选择。然后，从4中选择将从第一个出来。换句话说，我们将使用代替 .这个技巧允许计算Lehmer代码的下一个数字，并立即将其应用于列表。这正是工作原理。unpackunpack(n, [3, 4])unpack(n, [4, 3])nth_permutation()

我想提到的最后一件事是，这与阶乘数系统密切相关。再看第一棵树，如果我们想要长度为2的排列而没有重复项，我们可以跳过每秒一次的排列索引。这将为我们提供长度为 4 的 12 个排列，可以将其修剪为长度 2。unpack(i, [4, 3])

for (var i = 0; i < 12; i++) {
    var lehmer = unpack(i * 2, [4, 3, 2, 1]); // Factorial number system
    console.log(lehmer.slice(0, 2));
}