LeetCode 969 - Pancake Sorting

https://leetcode.com/problems/pancake-sorting/

Given an array A, we can perform a pancake flip: We choose some positive integer k <= A.length, then reverse the order of the first k elements of A.  We want to perform zero or more pancake flips (doing them one after another in succession) to sort the array A.

Return the k-values corresponding to a sequence of pancake flips that sort A.  Any valid answer that sorts the array within 10 * A.length flips will be judged as correct.

Example 1:

Input: [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: A = [3, 2, 4, 1]
After 1st flip (k=4): A = [1, 4, 2, 3]
After 2nd flip (k=2): A = [4, 1, 2, 3]
After 3rd flip (k=4): A = [3, 2, 1, 4]
After 4th flip (k=3): A = [1, 2, 3, 4], which is sorted. 

Example 2:

Input: [1,2,3]
Output: []
Explanation: The input is already sorted, so there is no need to flip anything.
Note that other answers, such as [3, 3], would also be accepted.

Note:

1. 1 <= A.length <= 100
2. A[i] is a permutation of [1, 2, ..., A.length]

X. https://leetcode.com/problems/pancake-sorting/discuss/214213/JavaC%2B%2BPython-Straight-Forward

Find the index i of the next maximum number x.
Reverse i + 1 numbers, so that the x will be at A[0]
Reverse x numbers, so that x will be at A[x - 1].
Repeat this process N times.

Update:
Actually, I didn't use the condition permutation of [1,2,..., A.length].
I searched in the descending order of A.

Time Complexity:
O(N^2)

Find max
swap max to top
swap max to bottom
reduce size
repeat

    public List<Integer> pancakeSort(int[] A) {
        List<Integer> res = new ArrayList<>();
        for (int x = A.length, i; x > 0; --x) {
            for (i = 0; A[i] != x; ++i);
            reverse(A, i + 1);
            res.add(i + 1);
            reverse(A, x);
            res.add(x);
        }
        return res;
    }

    public void reverse(int[] A, int k) {
        for (int i = 0, j = k - 1; i < j; i++, j--) {
            int tmp = A[i];
            A[i] = A[j];
            A[j] = tmp;
        }
    }

https://leetcode.com/problems/pancake-sorting/discuss/214200/Java-flip-the-largest-number-to-the-tail

1. Find the largest number
2. Flip twice to the tail

    public List<Integer> pancakeSort(int[] A) {
        List<Integer> result = new ArrayList<>();
        int n = A.length, largest = n;
        for (int i = 0; i < n; i++) {
            int index = find(A, largest);
            flip(A, index);
            flip(A, largest - 1);
            result.add(index + 1);
            result.add(largest--);
        }
        return result;
    }
    private int find(int[] A, int target) {
        for (int i = 0; i < A.length; i++) {
            if (A[i] == target) {
                return i;
            }
        }
        return -1;
    }
    private void flip(int[] A, int index) {
        int i = 0, j = index;
        while (i < j) {
            int temp = A[i];
            A[i++] = A[j];
            A[j--] = temp;
        }
    }

https://leetcode.com/articles/pancake-sorting/
Approach 1: Sort Largest to Smallest

We can place the largest element (in location i, 1-indexed) by flipping i to move the element to the first position, then A.length to move it to the last position. Afterwards, the largest element is in the correct position, so we no longer need to pancake-flip by A.length or more.

We can repeat this process until the array is sorted. Each move will use 2 flips per element.

First, sort the locations from largest value of A to smallest value of A.

For each element (from largest to smallest) with location i, we will first simulate where this element actually is, based on the pancake flips we have done. For a pancake flip f, if i <= f, then the element has moved from location i to f+1 - i.

After, we flip by i then N-- to put this element in the correct position.

• Time Complexity: $O(N^2)$, where $N$ is the length of A.
• Space Complexity: $O(N)$.

  public List<Integer> pancakeSort(int[] A) {

    List<Integer> ans = new ArrayList();

    int N = A.length;

    Integer[] B = new Integer[N];

    for (int i = 0; i < N; ++i)

      B[i] = i + 1;

    Arrays.sort(B, (i, j) -> A[j - 1] - A[i - 1]);

    for (int i : B) {

      for (int f : ans)

        if (i <= f)

          i = f + 1 - i;

      ans.add(i);

      ans.add(N--);

    }

    return ans;

  }

X. https://www.acwing.com/solution/LeetCode/content/753/
(倒推) O(n2)O(n2)
假设我们现在面对一个有序的数组 cur，期望通过以上操作将其变回数组 A。
我们从数组末尾开始往开头匹配，如果 cur 的当前元素 cur[i] 与 A[i] 不一致，则在 i 之前的元素中检索 A[i]。
找到 k 使得 cur[k] = A[i]；如果 k = 1，则直接做一次翻转即可将 cur[k] 放到 cur[i] 处；否则需要先将 cur[k] 放到 cur[1] 处，然后再将 cur[1] 放到 cur[i] 处。
如此循环直到完成所有数字的匹配，将 ans 数组倒置就是答案。
时间复杂度
共有 O(n)O(n) 个位置需要匹配，每次检索和移动数组同样需要 O(n)O(n) 的时间，故总时间复杂为 O(n^2)。

    vector<int> pancakeSort(vector<int>& A) {
        int n = A.size();
        vector<int> cur(n), ans;

        for (int i = 0; i < n; i++)
            cur[i] = i + 1;

        for (int i = n - 1; i >= 0; i--) {
            if (cur[i] != A[i]) {
                int k = -1;
                for (int j = 0; j < i; j++)
                    if (cur[j] == A[i]) {
                        k = j;
                        break;
                    }

                if (k > 0) {
                    reverse(cur.begin(), cur.begin() + k + 1);
                    ans.push_back(k + 1);
                }
                reverse(cur.begin(), cur.begin() + i + 1);
                ans.push_back(i + 1);
            }
        }
        reverse(ans.begin(), ans.end());

        return ans;
    }
https://zhanghuimeng.github.io/post/leetcode-969-pancake-sorting/

1. 直接模拟的复杂度为O(N^2)（因为每次翻转操作的复杂度是O(N)），能否降低复杂度？
2. 这样得到的是否为最优解？

第二个问题的答案是，显然不是，这种做法只是给出了一个上界（至多2*N - 3次翻转必然可以完成排序，至于为什么少了3次，请考虑只剩1和2时的情形）。而且找到最优解是一个NP-难问题。那么我就不再耗费我可怜的脑细胞在这个问题上了。顺便一提，比尔·盖茨证明了这个问题的上界是5(N+5) / 3；目前最优的结果是18N / 11。[1]

X. Follow up: sort the array in a minimum number of moves

X. https://www.geeksforgeeks.org/pancake-sorting/

Given an an unsorted array, sort the given array. You are allowed to do only following operation on array.

flip(arr, i): Reverse array from 0 to i 

Unlike a traditional sorting algorithm, which attempts to sort with the fewest comparisons possible, the goal is to sort the sequence in as few reversals as possible.

The idea is to do something similar to Selection Sort. We one by one place maximum element at the end and reduce the size of current array by one.

Following are the detailed steps. Let given array be arr[] and size of array be n.
1) Start from current size equal to n and reduce current size by one while it’s greater than 1. Let the current size be curr_size. Do following for every curr_size
……a) Find index of the maximum element in arr[0..curr_szie-1]. Let the index be ‘mi’
……b) Call flip(arr, mi)
……c) Call flip(arr, curr_size-1)

Total O(n) flip operations are performed in above code. The overall time complexity is O(n^2).

    static void flip(int arr[], int i)

    {

        int temp, start = 0;

        while (start < i)

        {

            temp = arr[start];

            arr[start] = arr[i];

            arr[i] = temp;

            start++;

            i--;

        }

    }

  

    // Returns index of the 

    // maximum element in 

    // arr[0..n-1] 

    static int findMax(int arr[], int n)

    {

        int mi, i;

        for (mi = 0, i = 0; i < n; ++i)

            if (arr[i] > arr[mi])

                mi = i;

        return mi;

    }

  

    // The main function that

    // sorts given array using 

    // flip operations

    static int pancakeSort(int arr[], int n)

    {

        // Start from the complete

        // array and one by one

        // reduce current size by one

        for (int curr_size = n; curr_size > 1; --curr_size)

        {

            // Find index of the

            // maximum element in

            // arr[0..curr_size-1]

            int mi = findMax(arr, curr_size);

  

            // Move the maximum element

            // to end of current array

            // if it's not already at 

            // the end

            if (mi != curr_size-1)

            {

                // To move at the end,

                // first move maximum

                // number to beginning

                flip(arr, mi);

  

                // Now move the maximum 

                // number to end by

                // reversing current array

                flip(arr, curr_size-1);

            }

        }

        return 0;

    }