Permutationen kleiner und großer Elemente

Question

Wenn das Array ist : 2,3,7,9; dann sind die Möglichkeiten, wie wir Permutationen haben können:

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.

Hier ist die Einschränkung:

1. Sobald ein Element ausgewählt ist, muss das nächste Element größer sein.
2. Das nächste Element danach muss kleiner als das vorherige sein und so weiter bis zum letzten Element.

Ich habe unten Code, aber ich bin nicht in der Lage, die Logik für Permutationen zu erhalten:

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);

Basierend auf Kommentaren:

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]

Answer 1

Diese Art der Permutation wird als Zickzack- oder alternierende Permutation bezeichnet

Es ist bekannt, dass die Anzahl solcher Permutationen von nElementen mit einer wiederkehrenden Formel beschrieben werden kann:

A(n+1) = Sum(k=0..n){C(n,k)*A(k)*A(n-k)} / 2

wo A(n)ist die Anzahl der Permutation der nElemente, initial A[] = 1, C(n,k)ist Binomialkoeffizient

So können wir das Array Schritt für Schritt mit berechneten Einträgen füllen

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]