CODEWITHSUNDEEP
algorithm
Devansh Singh
Devansh Singh

Reputation: 3

recursive formula which gives number of permutations?

Is there any recursive formula which gives number of permutations each of which can be reduced to ordered permutation by certain number of flips for n pancakes by using pancake sort algorithm?

Upvotes: 0

Views: 241

Answers (1)

btilly
btilly

Reputation: 46408

I do not have a proof, but would be willing to bet a large sum of money that there is not such, unless you restrict the number of flips to be small.

There is no trouble recursively counting how many ways of performing the flipping operations there are. The challenge is in figuring out how many other ways there are to arrive at the same order with a different sequence of flips. In fact per https://en.wikipedia.org/wiki/Pancake_sorting#The_pancake_problems, finding the shortest sequence of flips to arrive at a particular order is NP-hard. Which means that if you have more than a few flips, the appropriate expressions to identify when there was another will have a combinatorial explosion.

If you want permutations that can be undone by the selection sort algorithm in n steps, there is a way to calculate it recursively in a way that is suited to dynamic programming.

Let f(n, m, on_top) be the number of permutations that can be solved in n steps, with m being the largest one out of place, and on_top is a variable that says whether the largest one out of place is on top of the stack. As a special case we'll say that f(0, 0, True) = 1 representing the sorted stack requiring no sorting.

Now our recursive rules are as follows:

  1. Base case: f(0, 0, True) = 1
  2. Second base case: if 0 < n then f(n, 0, False) = f(n, 0, True) = 0
  3. Third base case: if 0 < m then f(0, m, True) = f(0, m, False) = 0
  4. Case where we will put the largest on top: f(n, m, False) = (m-2) * f(n-1, m, True). The reason why it is this is that the mth pancake must be in the top m-1 locations because it is out of place and nothing larger is displaced. But it can't be on top because then the last argument would be True and it is not. So that gives m-2 possible flips we would have to do.
  5. Case where we will put the largest in its place: f(n, m, True) = sum over i < m of (f(n-1, i, False) + f(n-1, i, True)). Which is just that we flip to put the largest in its place, and then come up with the next largest out of place.

This is enough to allow us to write a recursive function that will calculate the answer. Unfortunately calculating that function naively will involve a lot of repeated calls. However if we memoize this function by saving the value you get for a set of parameters and returning it again the next time, then you'll short-circuit most of the calculation and evaluating this will only take a polynomial amount of work.

Upvotes: 1

Related Questions