Блог

Если массив равен : 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.
  

Здесь ограничение заключается в :

1. Как только элемент выбран, следующий элемент должен быть больше его.
2. Следующий элемент после этого должен быть меньше предыдущего, и так далее до последнего элемента.

У меня есть приведенный ниже код, но я не могу получить логику для перестановок:

 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]