算法題丨Next Permutation

描述

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

示例

Here are some examples. Inputs are in the left-hand column 
and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1           

算法分析

難度：中

分析：這裡需要跟大家介紹一下相關的幾個概念：

排列（Arrangement），簡單講是從N個不同元素中取出M個，按照一定順序排成一列，通常用A(M,N)表示。當M=N時，稱為全排列（Permutation）。

例如對于一個集合A={1,2,3}，首先擷取全排列a1: 1,2,3；然後擷取下一個排列a2: 1,3,2；

按此順序，A的全排列如下，共6種：

a1: 1,2,3;　　a2: 1,3,2;　　a3: 2,1,3;　　a4: 2,3,1;　　a5: 3,1,2;　　a6: 3,2,1;　　

從數學角度講，全排列的個數A(N,N)=(N)*(N-1)*...*2*1=N!，但從程式設計角度，如何擷取所有排列？那麼就必須按照某種順序逐個獲得下一個排列，通常按照升序順序（字典序lexicographically）獲得下一個排列。

對于給定的任意一種全排列，如果能求出下一個全排列的情況，那麼求得所有全排列情況就容易了，也就是題目要求實作的下一個全排列算法（Next Permutation）。

思路：

設目前有一個集合的一種全排列情況A : 1,5,8,4,7,6,5,3,1，求取下一個排列的步驟如下：

/** Tips: next permuation based on the ascending order sort
 * sketch :
 * current: 1   5  8  4  7  6  5  3  1
 *                    |        |     |
 *          find i----+        j     +----end
 * swap i and j :
 *          1   5  8  5  7  6  4  3  1
 *                    |        |     |
 *               j----+        i     +----end
 * reverse j+1 to end :
 *          1   5  8  5  1  3  4  6  7
 *                    |              |
 *          find j----+              +----end
 * */           

具體方法為：

a）從後向前查找第一個相鄰元素對(i,i+1)，并且滿足A[i] < A[i+1]。

易知，此時從j到end必然是降序。可以用反證法證明，請自行證明。

b）在[i+1,end)中尋找一個最小的j使其滿足A[i]<A[j]。

由于[j,end)是降序的，是以必然存在一個j滿足上面條件；并且可以從後向前查找第一個滿足A[i]<A[j]關系的j，此時的j必是待找的j。

c）将i與j交換。

此時，i處變成比i大的最小元素，因為下一個全排列必須是與目前排列按照升序排序相鄰的排列，故選擇最小的元素替代i。

易知，交換後的[j,end)仍然滿足降序排序。

d）逆置[j,end)

由于此時[j,end)是降序的，故将其逆置。最終獲得下一全排序。

注意：如果在步驟a）找不到符合的相鄰元素對，即此時i=begin，則說明目前[begin,end)為一個降序順序，即無下一個全排列，于是将其逆置成升序。

代碼示例(C#)

public void NextPermutation(int[] nums)
{
    int i = nums.Length - 2;
    //末尾向前查找，找到第一個i，使得A[i] < A[i+1]
    while (i >= 0 && nums[i + 1] <= nums[i])
    {
        i--;
    }
    if (i >= 0)
    {
        //從i下标向後找第一個j,使得A[i]<A[j]
        int j = nums.Length - 1;
        while (j >= 0 && nums[j] <= nums[i])
        {
            j--;
        }
        //交換i，j
        Swap(nums, i, j);
    }
    //逆置j之後的元素
    Reverse(nums, i + 1, nums.Length);
} 
    
//逆置排序
private void Reverse(int[] nums, int start, int end)
{
    int i = start, j = end - 1;
    while (i < j)
    {
        Swap(nums, i, j);
        i++;
        j--;
    }
}

//交換
private void Swap(int[] nums, int i, int j)
{
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}            

複雜度

• 時間複雜度：O (n).
• 空間複雜度：O (1).

附錄

• 系列目錄索引
• 代碼實作(C#版)
• 相關算法： Permutation Sequence

文章作者：原子蛋

文章出處：

https://www.cnblogs.com/lizzie-xhu/ 個人網站： https://www.lancel0t.cn/ 個人部落格： https://blog.lancel0t.cn/

微信公衆号：原子蛋Live+

掃一掃左側的二維碼（或者長按識别二維碼），關注本人微信公共号，擷取更多資源。

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。