{"action":"created","issue":{"url":"https://api.github.com/repos/cbweixin/algorithm-practice/issues/143","repository_url":"https://api.github.com/repos/cbweixin/algorithm-practice","labels_url":"https://api.github.com/repos/cbweixin/algorithm-practice/issues/143/labels{/name}","comments_url":"https://api.github.com/repos/cbweixin/algorithm-practice/issues/143/comments","events_url":"https://api.github.com/repos/cbweixin/algorithm-practice/issues/143/events","html_url":"https://github.com/cbweixin/algorithm-practice/issues/143","id":124603033,"number":143,"title":"Next Permutation","user":{"login":"cbweixin","id":1326906,"avatar_url":"https://avatars.githubusercontent.com/u/1326906?v=3","gravatar_id":"","url":"https://api.github.com/users/cbweixin","html_url":"https://github.com/cbweixin","followers_url":"https://api.github.com/users/cbweixin/followers","following_url":"https://api.github.com/users/cbweixin/following{/other_user}","gists_url":"https://api.github.com/users/cbweixin/gists{/gist_id}","starred_url":"https://api.github.com/users/cbweixin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cbweixin/subscriptions","organizations_url":"https://api.github.com/users/cbweixin/orgs","repos_url":"https://api.github.com/users/cbweixin/repos","events_url":"https://api.github.com/users/cbweixin/events{/privacy}","received_events_url":"https://api.github.com/users/cbweixin/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":0,"created_at":"2016-01-02T18:04:22Z","updated_at":"2016-02-29T18:46:38Z","closed_at":null,"body":"### Problem\r\n Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.\r\n\r\nIf such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).\r\n\r\nThe replacement must be in-place, do not allocate extra memory.\r\n\r\nHere are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.\r\n\r\n    1,2,3 → 1,3,2\r\n    3,2,1 → 1,2,3\r\n    1,1,5 → 1,5,1\r\n\r\n### Analysis\r\nhere is a next permuation sequence:\r\n\r\n    [3,1,2,4,5]\r\n    [3,1,2,5,4]\r\n    [3,1,4,2,5]\r\n    [3,1,4,5,2]\r\n    [3,1,5,2,4]\r\n    [3,1,5,4,2]\r\n\r\nnotice `(2,4,5)` -> `(2,5,4)` -> `(4,2,5)` -> `(4,5,2)` -> `(5,2,4)` -> `(5,4,2)`\r\n\r\nso the algorithm is :+1: \r\n-  firstly for 2,4,5, you can get 2,4,5\r\n- then fix 4, look for a number which is bigger than 4 , swap it, you get 2, 5, 4\r\n- now 2 | 5,4 , (5,4) is already reverse ordered, so you have to go to 2, find another number which is bigger than 2, but 4, and 5 are all bigger than 2, so you choose the smallest one which is bigger than 2, this is 4. \r\n- then you get 4,5,2, sort the 5,2, you get 4, 2, 5\r\n- then 4, 5, 2\r\n- then 5,2 is fully revrese ordered, then find another number bigger than 4, which is 5. \r\n- you get 5,4,2, by swapping , then u sort them, you get 5, 2,4 . \r\n- a special case, if you get 5,4 2. then all the numbers are fully reverse-ordered, so you just need to sort it to be 2,4,5, like a cycle. \r\n\r\n### Attempt 1\r\n```c++\r\nclass Solution {\r\npublic:\r\n    void nextPermutation(vector<int>& nums) {\r\n        if(nums.empty()) return;\r\n        \r\n        int len = nums.size();\r\n        int i = len-1;\r\n        for( ;i >= 1;i--){\r\n            if(nums[i] > nums[i-1]){\r\n                break;\r\n            }\r\n        }\r\n        \r\n        if(i==0)\r\n        {\r\n            sort(nums.begin(), nums.end());\r\n        }\r\n        else{\r\n             int j = i;\r\n            int smallestBig = INT_MAX, smallestIdx = -1;\r\n            for( ; j < len; j++){\r\n                if(nums[j] > nums[i-1]){\r\n                    if(nums[j] < smallestBig){\r\n                     smallestBig = nums[j];\r\n                     smallestIdx = j;\r\n                    }\r\n                }\r\n            }\r\n        \r\n            swap(nums[i-1], nums[smallestIdx]);\r\n            sort(nums.begin() + i, nums.end() );\r\n            \r\n        }\r\n    }\r\n};\r\n```\r\n\r\n#### Result\r\n![image](https://cloud.githubusercontent.com/assets/1326906/12076191/72f0115c-b155-11e5-8a28-63f8fd8f6bcc.png)\r\n\r\n#### Analysis\r\n- for the end of the array, go backwards, find the first element which break the descending order. for ex, test case 2,5,4,3,1, `5,4,3,2` is descending order, but `2` breaks this order. \r\n```c++\r\n  for( ;i >= 1;i--){\r\n            if(nums[i] > nums[i-1]){\r\n                break;\r\n            }\r\n        }\r\n```\r\n- for special case, all numbers are in descending order, then sort all of them\r\n```c++\r\n if(i==0)\r\n        {\r\n            sort(nums.begin(), nums.end());\r\n        }\r\n```\r\n- else, assume we find an element at position i-1 which breaks this order, then from `nums[i]` to `nums.end()`, find the smallest element which is bigger than `nums[i-1]`. \r\n```c++\r\n int j = i;\r\n            int smallestBig = INT_MAX, smallestIdx = -1;\r\n            for( ; j < len; j++){\r\n                if(nums[j] > nums[i-1]){\r\n                    if(nums[j] < smallestBig){\r\n                     smallestBig = nums[j];\r\n                     smallestIdx = j;\r\n                    }\r\n                }\r\n            }\r\n```\r\n- then swap the elemetn `nums[i-1]`, and the element which find in the previous step ,\r\n```c++\r\n  swap(nums[i-1], nums[smallestIdx]);\r\n```\r\n- finally sort the element from nums[i] to nums.end();\r\n\r\n### Reference 1\r\n```c++\r\nclass Solution {\r\npublic:\r\n    void nextPermutation(vector<int>& nums) {\r\n        int index = 0,swapindex = 0;\r\n        for (int i = 1; i < nums.size(); i++)\r\n            if  (nums[i - 1] < nums[i])\r\n                index = i;\r\n        if (index > 0){\r\n            int i = nums.size() - 1;\r\n            while (i > (index - 1) && nums[index-1] >= nums[i]) i--;\r\n            swap(nums[index - 1],nums[i]);\r\n        }\r\n        sort(nums.begin() + index,nums.end());\r\n    }\r\n};\r\n```\r\n### Attempt 2\r\n```c++\r\nclass Solution {\r\npublic:\r\n    void nextPermutation(vector<int>& nums) {\r\n        if(nums.empty()) return;\r\n        \r\n        int len = nums.size();\r\n        int i = len-1;\r\n        for( ;i >= 1;i--){\r\n            \r\n            if(nums[i] > nums[i-1]){\r\n                break;\r\n            }\r\n        }\r\n        \r\n        if(i==0)\r\n        {\r\n            sort(nums.begin(), nums.end());\r\n        }\r\n        else\r\n        {\r\n            int j = len-1;\r\n            while(j > i - 1 && nums[j] < nums[i-1]){\r\n                j--;\r\n            }\r\n                \r\n            swap(nums[i-1], nums[j]);\r\n            sort(nums.begin() + i, nums.end() );\r\n            \r\n        } \r\n    }\r\n};\r\n```\r\n\r\n#### Result\r\n![image](https://cloud.githubusercontent.com/assets/1326906/12076630/2f426352-b168-11e5-8a49-cf6b500e1a62.png)\r\n\r\n\r\n#### Analysis\r\nthe critical part is :-1:  ` while(j > i - 1 && nums[j] < nums[i-1]){`\r\n\r\n### Attempt 3\r\n```c++\r\nclass Solution {\r\npublic:\r\n    void nextPermutation(vector<int>& nums) {\r\n        if(nums.empty()) return;\r\n        \r\n        int len = nums.size();\r\n        int i = len-1;\r\n        for( ;i >= 1;i--){\r\n            \r\n            if(nums[i] > nums[i-1]){\r\n                break;\r\n            }\r\n        }\r\n        \r\n        if(i==0)\r\n        {\r\n            sort(nums.begin(), nums.end());\r\n        }\r\n        else\r\n        {\r\n            int j = len-1;\r\n            while(j > i - 1 && nums[j] <= nums[i-1]){\r\n                j--;\r\n            }\r\n                \r\n            swap(nums[i-1], nums[j]);\r\n            sort(nums.begin() + i, nums.end() );\r\n            \r\n        }\r\n    }\r\n};\r\n```\r\n\r\n#### Result\r\n![image](https://cloud.githubusercontent.com/assets/1326906/12076633/4fbce4f4-b168-11e5-8ee2-814dc2f42e6d.png)\r\n\r\nAlthough passed the test, but compared with code in Reference 1, still not concise enough. still a long way to go. \r\n\r\n"},"comment":{"url":"https://api.github.com/repos/cbweixin/algorithm-practice/issues/comments/190328815","html_url":"https://github.com/cbweixin/algorithm-practice/issues/143#issuecomment-190328815","issue_url":"https://api.github.com/repos/cbweixin/algorithm-practice/issues/143","id":190328815,"user":{"login":"cbweixin","id":1326906,"avatar_url":"https://avatars.githubusercontent.com/u/1326906?v=3","gravatar_id":"","url":"https://api.github.com/users/cbweixin","html_url":"https://github.com/cbweixin","followers_url":"https://api.github.com/users/cbweixin/followers","following_url":"https://api.github.com/users/cbweixin/following{/other_user}","gists_url":"https://api.github.com/users/cbweixin/gists{/gist_id}","starred_url":"https://api.github.com/users/cbweixin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cbweixin/subscriptions","organizations_url":"https://api.github.com/users/cbweixin/orgs","repos_url":"https://api.github.com/users/cbweixin/repos","events_url":"https://api.github.com/users/cbweixin/events{/privacy}","received_events_url":"https://api.github.com/users/cbweixin/received_events","type":"User","site_admin":false},"created_at":"2016-02-29T18:46:38Z","updated_at":"2016-02-29T18:46:38Z","body":"REDO\r\n\r\n### Attempt 1\r\n```java\r\npublic class Solution {\r\n    public void nextPermutation(int[] nums) {\r\n       int k = nums.length-1;\r\n       \r\n       int i = k;\r\n       for(; i >0; i-- ){\r\n           if(nums[i]>nums[i-1]){\r\n               int idx = getBigger(nums, i, nums[i-1]);\r\n               swap(nums,i-1, idx);\r\n               Arrays.sort(nums, i, nums.length);\r\n               break;\r\n           }\r\n       }\r\n       if(i==0) Arrays.sort(nums);\r\n       \r\n    }\r\n    \r\n    private int getBigger(int[] nums, int idx, int target){\r\n        for(int k = nums.length-1; k >= idx; k--){\r\n            if(nums[k] > target){\r\n                return k;\r\n            }\r\n        }\r\n        return -1;\r\n    }\r\n    \r\n    private void swap(int[] nums, int i, int j){\r\n        int temp = nums[i];\r\n        nums[i] = nums[j];\r\n        nums[j] = temp;\r\n    }\r\n}\r\n```\r\n\r\n#### Result\r\n![image](https://cloud.githubusercontent.com/assets/1326906/13405097/b2ae9616-ded1-11e5-8aec-f1af44406dfc.png)\r\n"}}