CODEWITHSUNDEEP
functionnumbersstackdiscrete-mathematicscatalan
alhid
alhid

Reputation: 61

Maths: Find permutation number using one stack

It's more a math problem I guess, nothing programming.

Suppose I have a stack and I want to find the permutations of numbers 1,2,3,...n. I can push and pop. e.g. if n=2: push,pop,push,pop 1,2 and push,push,pop,pop 2,1

if n=4 I can only get 14 from the 24 permutations using the stack.. Does anyone know any function F(n) that could produce the number of permutations the stack (only one) can produce? eg f(1)=1

f(2)=2

f(4)=14

Upvotes: 3

Views: 992

Answers (2)

schnaader
schnaader

Reputation: 49729

I think there is some quite easy formula for that. You're looking for permutations of N push operations ("X") and N pop ("Y") operations, following one simple rule:

  • No pop on an empty stack (f.e. Y.... and XXYYY... are invalid)

Perhaps some recursive definition helps:

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

Upvotes: 0

konrad.kruczynski
konrad.kruczynski

Reputation: 47641

Such function is a Catalan number. See http://en.wikipedia.org/wiki/Catalan_number for the formula.

Upvotes: 3

Related Questions