Математика: Найти номер перестановки, используя один стек

Question

Это, скорее, математическая задача, ничего не программируя.

Предположим, у меня есть stack, и я хочу найти permutations чисел 1,2,3,...n.Я могу push и pop.например, если n = 2: push,pop,push,pop 1,2 и push,push,pop,pop 2,1

, если n = 4, я могу получить 14 только из перестановок 24, используя stack.Кто-нибудь знает какой-нибудь function F(n), который может произвести число permutations, которое может произвести стек (только один)?например, f (1) = 1

f (2) = 2

f (4) = 14

Answer 1

Такой функцией является каталонское число.См. http://en.wikipedia.org/wiki/Catalan_number для формулы.

Answer 2

Я думаю, что есть довольно простая формула для этого.Вы ищете перестановки операций N push («X») и N pop («Y»), следуя одному простому правилу:

• Нет пустых стеков (например, Y .... и XXYYY ... недействительны)

Возможно, поможет какое-то рекурсивное определение:

function F(n_push, n_pop) {
  int total_count = 0;

  if (n_push > 0) total_count += F(n_push - 1, n_pop);
  if (n_pop > n_push) total_count += F(n_push, n_pop - 1);

  return total_count;
}