Find number of permutations using Stack

21^st, July, 2010

Find number of permutations

Assume we are receiving a stream of integers (1, 2, 3, 4, 5, … N). Using stack data structure (FIFO), find how many different permutations of the ordered stream is possible?

Solution: Interestingly, the answer is Catalan number.

A stack is a First In First Out data structure. The integers shall be pushed and popped in the order of their appearance in the input stream. Say, P(N) as possible permutations of the input stream. Let k representing an integer in the stream, hence the stack should contain k-1 elements and N-k-1 elements are in pipeline from the stream.

Fixing k position, the k-1 elements can be pushed and popped in (k-1)! ways. Similarly, the upcoming N-k-1 elements. In other words, there are P(k) permutations possible with the elements in the stack and P(N-k-1) permutations are possible with the upcoming integers. But, k can range from 1 to N, using multiplication and addition principle we get,

P(N) = ∑ P(k-1)P(N-k-1), k ranging from 1 to N, and P(1) = 1.

The expression P(N) is recursive. After expanding, we get Segner’s expression which can be represented in Catalan number.

P(N) = (2NcN)/(N+1) – Catalan Number C(N)

The above expression resembles the Catalan number. The Catalan numbers are ubiquitous.

Note that there are N! possible permutations using N integers, however, P(N) < N!. It is due to the definition of stack data structure.