algorithm - 计算数组的排列

Question

假设我们有一个长度为 z 的数组。其中由 x 个不同的偶数和 y 个不同的奇数组成。

所以 z = x+y。

我们还知道 x => 1 始终适用。

第一个问题:有多少个长度为 z 的不同数组。那应该正好是z!许多或？

第二个问题:有多少个不同的数组，使得数组中的最后一个偶数在奇数索引上。 (本例中的数组从索引1开始)

例子:

1) [1,2,3,4,5] 这个数组的长度是5，数组最后一个偶数是4，数组的下标是4，所以这样的数组我们不算。

2) [52,3,14]。该数组中的最后一个偶数是 14，索引为 3。因此这样的数组计入它。

3) [52,3,5,7]。该数组中的最后一个偶数是 52，索引为 1。因此，这样的数组也计入它。

我根本找不到解决这个问题的好方法。特别是，我会对动态规划的解决方案感兴趣。

Answer 1

第一个问题:有z!数组，除非数组中有重复的数字。公式如下:n!/((n1!)(n2!)(n3!)...(nz!))，其中 n1 是第一个数字的次数数组重复，n2 第二个数字重复的次数..等等。