Java 中的排列系数

排列可以定义为，将给定集合的所有成员排列成一个序列的过程。排列系数用 P(n, r) 表示。它表示从 n 个元素中每次取 r 个元素的排列数。因此，如果我们必须计算 P(5, 2)，则表示有 5 个元素（n = 5），并且可以从中取任意 2 个元素（r = 2），任务是找出取这 2 个元素的方法数。在本节中，我们将讨论排列系数及其计算方法。此外，我们还将为此创建一个 Java 程序。

假设这 5 个元素是 1、2、3、4 和 5，我们可以取的 2 个元素是

(1, 2) (1, 3) (1, 4) (1, 5)

(2, 1) (2, 3) (2, 4) (2, 5)

(3, 1) (3, 2) (3, 4) (3, 5)

(4, 1) (4, 2) (4, 3) (4, 5)

(5, 1) (5, 2) (5, 3) (5, 5)

如果我们计算提到的对，我们会得到 20。因此，从 5 个元素（1、2、3、4、5）的集合中取这 2 个元素有 20 种方法。

在数学上，我们可以使用以下公式计算 P(n, r) 的值

因此，

P(5, 2) = 5! / (5 - 2)! = 5! / 3! = (5 x 4 x 3 x 2 x 1) / (3 x 2 x 1) = 120 / 6 = 20

P(7, 4) = 7! / (7 - 4)! = 7! / 3! = (7 x 6 x 5 x 4 x 3 x 2 x 1) / (3 x 2 x 1) = 5040 / 6 = 840

注意

• 当 r = 0 时，P(n, r) 的值始终为 1。
  P(n, 0) = n! / (n - 0)! = n! / n! = 1
• 当 r = n 时，P(n, r) 的值始终为 n!。
  P(n, n) = n! / (n - n)! = n! / 0! = n! / 1 = n! (0! 始终为 1)

实施

让我们通过一个 Java 程序来计算 P(n, r) 的值。

使用数组

文件名： PermCoefficient.java

输出

The value of (7, 4) is: 840

The value of (5, 2) is: 20

时间复杂度：上述程序的复杂度为 O(n + r)。这是因为 findFactorial() 方法中提到的 for 循环执行两次：一次用于值 n，另一次用于值 r。

另一种方法

找到 P(n, r) 值的另一种方法如下所述。

P(n, r) = P(n - 1, r) + r x P(n - 1, r - 1)

如果 n < r，则 P(n, r) = 0

并且

P(n, 0) = 1

&

P(n, n) = n!

&

P(n, 1) = n

因此，

P(10, 2) = P(10 - 1, 2) + 2 x P(10 - 1, 2 - 1)

P(10, 2) = P(9, 2) + 2 x P(9, 1)

P(10, 2) = P(9, 2) + 2 x 9 = P(9, 2) + 18           - 方程 A

现在，我们将计算 P(9, 2) 的值

P(9, 2) = P(9 - 1, 2) + 2 x P(9 - 1, 2 - 1)

= P(8, 2) + 2 x P(8, 1)           - 方程 B

= P(8, 2) + 2 x 8 = P(8, 2) + 16

P(8, 2) = P(8 - 1, 2) + 2 x P(8 - 1, 2 - 1)

= P(7, 2) + 2 x P(7, 1)

= P(7, 2) + 2 x 7 = P(7, 2) + 14           - 方程 C

P(7, 2) = P(7 - 1, 2) + 2 x P(7 - 1, 2 - 1)

= P(6, 2) + 2 x P(6, 1)

= P(6, 2) + 2 x 6 = P(6, 2) + 12           - 方程 D

P(6, 2) = P(6 - 1, 2) + 2 x P(6 - 1, 2 - 1)

= P(5, 2) + 2 x P(5, 1)

= P(5, 2) + 2 x 5 = P(5, 2) + 10           - 方程 E

P(5, 2) = P(5 - 1, 2) + 2 x P(5 - 1, 2 - 1)

= P(4, 2) + 2 x P(4, 1)

= P(4, 2) + 2 x 4 = P(4, 2) + 8           方程 F

P(4, 2) = P(4 - 1, 2) + 2 x P(4 - 1, 2 - 1)

= P(3, 2) + 2 x P(3, 1)

= P(3, 2) + 2 x 3 = P(3, 2) + 6           方程 G

P(3, 2) = P(3 - 1, 2) + 2 x P(3 - 1, 2 - 1)

= P(2, 2) + 2 x P(2, 1)

= 2! + 2 x 2 = 2 x 1 + 2 x 2 = 2 + 4 = 6

将 P(3, 2) 的值代入方程 G，我们得到

P(4, 2) = P(3, 2) + 6 = 6 + 6 = 12

将 P(4, 2) 的值代入方程 F，我们得到

P(5, 2) = P(4, 2) + 8 = 12 + 8 = 20

将 P(5, 2) 的值代入方程 E，我们得到

P(6, 2) = P(5, 2) + 10 = 20 + 10 = 30

将 P(6, 2) 的值代入方程 D，我们得到

P(7, 2) = P(6, 2) + 12 = 30 + 12 = 42

将 P(7, 2) 的值代入方程 C，我们得到

P(8, 2) = P(7, 2) + 14 = 42 + 14 = 56

将 P(8, 2) 的值代入方程 B，我们得到

P(9, 2) = P(8, 2) + 16 = 56 + 16 = 72

将 P(9, 2) 的值代入方程 A，我们得到

P(10, 2) = P(9, 2) + 18 = 72 + 18 = 90

递归方法

让我们用递归看看实现。

文件名： PermutationCoeff.java

输出

The Value of P(10, 2) is: 90
The Value of P(7, 3) is: 210

迭代方法-1

让我们看看使用嵌套 for 循环和二维数组的实现。

文件名： PermutationCoeff1.java

输出

The Value of P(10, 2) is: 90

The Value of P(7, 3) is: 210

在上面的程序中，我们使用了嵌套 for 循环来计算 P(n, r) 的值。由于嵌套 for 循环，该程序的复杂度为 O(n * r)。空间复杂度也为 O(n * r)。但是，我们可以进行优化，将时间和空间复杂度都降低到 O(n)。

迭代方法-2

让我们看看使用单个 for 循环和一维数组的实现。

文件名： PermutationCoeff2.java

输出

The Value of P(10, 2) is: 90

The Value of P(7, 3) is: 210

我们可以进一步优化并将空间复杂度降低到 O(1)。但是，时间复杂度仍然保持不变，即 O(n)。观察以下程序。

迭代方法-3

让我们看看使用单个 for 循环的实现。

文件名： PermutationCoeff3.java

输出

The Value of P(10, 2) is: 90

The Value of P(7, 3) is: 210