Next Permutation Algorithm，取得全排列中当前排列的下一个排列

清疚 2022-03-01 04:12 156阅读 0赞

# Next Permutation算法 #

给定一个整数数组，数组中的每一个元素均为0~9之间的整数，如下算法能够高效取得在该数组按数字从小到大排列的全排列中的下一个排列。给定一个任意整数数字，该算法亦可以用来找到仅使用该整数中的数字重构能够得到的 **最小的** 比当前数字大的数字。

假定输入数组为`nums`。

1.  找出当前数组中的 **第一个** 满足`nums[k] < nums[k + 1]`条件的索引`k`。如果满足该条件的索引`k`不存在，则当前数组为根据数字排序位于最后一位的排列。
2.  找出当前数组中 **最后一个** 满足`nums[j] > nums[lk]`条件的索引`j`。
3.  调换`nums[k]`与`nums[j]`的值。
4.  从`k+1`（包含`k+1`）开始，翻转从`k+1`到最后一个位置的所有数字。

# 算法理解 #

对于任意一个数组，如果其中所有数字均为倒序排列，则当前数组为排列组合中最大的数组。反之，如果其中所有数字均为正序排列，则当前数组为排列组合中最小的数组。因此我们将数组分为两部分。

第一步我们首先寻找数组后半段中无法再增大的子数组，也就是从`k+1`到`n-1`这一段。接着为了将数组增大一点，我们需要将这一段中比`k`大的最小的数字`j`与位置`k`的数字互换。我们需要寻找比当前数组大的最小数组（注意在我们的排序规则下越靠左的数字越大，越靠右的数字越小，类似于整数的数位），因此这一数字应当尽量小。寻找`j`的过程满足这一要求，也就是最后一位大于`k`的数字。在互换之后，数组从`k+1`到`n-1`这一段仍然是倒叙排列的（因为`j`是其中最后一位大于`k`的数字，也就是说从`k+1`到`j`任意一位都大于`k`，`j+1`到`n-1`任意一位都小于`k`），也就是这子数组最大的可能排列。又由于我们已经在`k`位置增大了当前数组（类比于整数中更高的数位被增大了），则我们应当尽量减小这一段子数组，所以我们应当翻转这一段来构造其可能的最小排列——顺序排列。

# 时间复杂度 #

`O(n)`。因为我们仅需循环整个数组一次。此处`n`为输入数组长度。

# 空间复杂度 #

`O(1)`。所有操作均为in-place操作。

# Java实现 #

public class NextPermutation {
        
        public void nextPermutation(int[] arr) {
        
            if (arr == null || arr.length == 0) {
        
                return;
            }
    
            int k = -1;
            for (int i = 0; i < arr.length - 1; i++) {
        
                if (arr[i] < arr[i + 1]) k = i;
            }
            if (k == -1) return;
    
            int j = -1;
            for (int i = 0; i < arr.length; i++) {
        
                if (arr[i] > arr[k]) j = i;
            }
            swap(arr, k, j);
    
            int start = k + 1, end = arr.length - 1;
            while (start < end) {
        
                swap(arr, start++, end--);
    
            }
        }
    
        private void swap(int[] arr, int i, int j) {
        
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }