S3E27. Narayana's next linear permutation algorithm

In this episode we trace a plausible honing in on an algorithm that can generate a lexicographically next linear permutation based solely on the information that is packed into the input (linear) permutation. Evidently, such a an algorithm was put together by an Indian mathematician Narayana Pandita (1340-1400) some time in the fourteenth century. We begin with an attempt to solve the problem of generating "all" linear permutations in any which way we can. And, it turns out, fairly quickly we can invent a naive "pend and paper" algorithm to do just that if we use the "Scope Reduction" or the "Reduce And Conquer" problem-solving approach. Once we understand how to generate all linear permutations of n distinct elements by-hand, we introduce a definition of a lexicographical order and, using that definition, we arrange all the permutations that were generated via our naive "pen and paper" algorithm in the order that is lexicographical. While we do that lexicographical ordering by-hand, we ponder: what single rule applied to any one such permutation will crank out the next one? The answer to that question, in this episode, is the Narayana's Next Linear Permutation Algorithm. We also share with our audience a sample implementation of that algorithm in the best programming language of all times, C.