Permutations de petits et grands éléments

Question

Si le tableau est le suivant : 2,3,7,9; alors les façons dont nous pouvons avoir des permutations sont:

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.

Ici, la restriction est:

1. Une fois qu'un élément est sélectionné, l'élément suivant doit être plus grand que lui.
2. L'élément suivant doit être plus petit que le précédent, et ainsi de suite jusqu'au dernier élément.

J'ai ci-dessous le code, mais je ne parviens pas à obtenir la logique des permutations:

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

Basé sur les commentaires:

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

Ce type de permutation est appelé zigzag ou permutations alternées

On sait que le nombre de ces permutations d' néléments pourrait être décrit avec une formule récurrente:

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

où A(n)est le nombre de permutation des néléments, initial A[] = 1, C(n,k)est le coefficient binomial

Nous pouvons donc remplir le tableau avec des entrées calculées étape par étape

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]