Recursive Algorithm to Generate Stack Permutations: An Exercise in Software Adaptation

摘要

A brute force method of generating stack permutations is to generate all permutations and then reject those that do not satisfy the stack permutation property. We develop a better (recursive) algorithm for generating stack permutations by adaptation of a formally derived recursive algorithm for generating permutations. We first analyze properties of stack permutations to arrive at a test condition which can be used in conjunction with the permutation algorithm. This test is then integrated into that algorithm to achieve the desired result. (ERA citation 08:038300)