0
$\begingroup$

i was implementing pan-cake sorting. We can implement it by taking largest element to start and flipping it recursively (Like selection sort).

However it is mentioned that the A[i] has to be a permutation of [1, 2, ..., A.length].

My question is, what if A[i] is not a permutation of [1,2,..., A.length]? How to solve that?

$\endgroup$
  • 1
    $\begingroup$ Sorry tedd but I do not see the point, i.e., for any arrangement of symbols you can always create a permutation by simply mapping each symbol in the arrangement with a natural number representing its desired location. As all symbols should be in different locations, a permutation naturally arises so that this problem is definitely a permutation state space problem. Maybe I missed some point though ... $\endgroup$ – Carlos Linares López Nov 28 '19 at 22:19
0
$\begingroup$

Let's suppose the input array is $A = [3,1,4,5,2]$. When sorting this array using pancake sorting, only flips of prefixes of the array are allowed. Flipping the first four elements, i.e. replacing $3145$ by $5413$, gives $A = [5,4,1,3,2]$. Then, flipping all five elements gives $[2,3,1,4,5]$, which brings the largest element to its correct position. By repeating this process to bring the next largest element to the last-but-one position, and so on, the array can be sorted.

The number of flips required to sort an array of length $n$ is at most $2n-3$. This is because bringing the largest $n-2$ elements to their correct positions can be done using at most $2n-4$ flips (because at most two flips are required for each element, as mentioned in previous paragraph). Finally, the elements in the first two positions can be sorted using at most one flip.

The problem of finding the minimum number of flips to pancake-sort an array is still open.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.