javascript - 小元素和大元素的排列
问题描述
如果数组是 : 2,3,7,9
; 那么我们可以进行排列的方式是:
2 7 3 9
2 9 3 7
3 7 2 9
3 9 2 7
7 9 2 3
so total ways are 5.
这里的限制是:
- 一旦选择了一个元素,下一个元素必须大于它。
- 这之后的下一个元素必须小于前一个元素,依此类推,直到最后一个元素。
我有以下代码,但我无法获得排列的逻辑:
let array = [2, 3, 7, 9];
array.sort((a, b) => a - b);
let res = [];
let n = array.length;
let i = 0;
let j = n - 1;
let k = 0;
while (i < j) {
res[k++] = array[i++];
res[k++] = array[j--];
}
if (n % 2 != 0) {
res[k++] = arr[i];
}
console.log(res);
根据评论:
function Factorial(n) {
var res=1;
for (var i = 2; i <= n; i++)
res = res * i;
return res;
}
let n = 4;
let A = [];
let C = [];
let a = Factorial(n);
for(let i=0; i<=n;i++) {
A[i] = 0;
}
A[1] = 1;
for(let k=0; k<n; k++) {
let b = Factorial(k)*Factorial(n-k);
A[k] = a/b * A[k]*A[n-k]/2;
}
console.log(A);
prints [0, 0, 0, 0]
解决方案
这种排列称为之字形排列或交替排列
已知n
元素的这种排列的数量可以用循环公式来描述:
A(n+1) = Sum(k=0..n){C(n,k)*A(k)*A(n-k)} / 2
其中A(n)
是n
项目的排列数initial A[] = 1
,C(n,k)
是二项式系数
所以我们可以一步一步地用计算的条目填充数组
function cnk(n, k) {
let res = 1;
for (let i = 0; i < k; i++)
res = res * (n - i) / (i + 1);
return res;
}
let m = 15;
let A = [1,1];
for (let i = 0; i < m-1; i++) {
A.push(0);
}
for (let n = 2; n < m; n++)
for (let k = 0; k <= n; k++)
A[n + 1] += A[k] * A[n - k] * cnk(n, k) / 2;
console.log(A);
[1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, 353792, 2702765,
22368256, 199360981, 1903757312]
推荐阅读
- asp.net-core - Razor 组件 (Blazor) - 影响派生类列表的渲染模式
- timer - 如何在 ARM Cortex-A7 中初始化内核定时器
- python - 错误:“pkg_resources.DistributionNotFound:未找到 'zipp>=0.5' 分发,并且 importlib-metadata 需要”
- django - 带有 digitalocean 的 docker 容器上的“DisallowedHost”问题
- cpu - 无法使用“mpirun”命令运行程序
- javascript - D3 JS使用路径在顶部而不是底部堆叠条
- python - 我在 Python3 中的快速排序打破了递归限制
- c# - 即使 streamreader 已关闭,使用 streamreader 后路径仍然不可用
- f# - 在 Deedle 中查找每个层次索引的 Stats.max
- reactjs - React autoFocus 属性未呈现