Java Full Arrangement Algorithm Dictionary Order Next Arrangement Explanation

1 Has written the algorithm of array full arrangement directly, at that time we touched back to ensure that the generated full arrangement 1 must be in dictionary order, but today when you do a question on leetcode, the problem is to find the next one in dictionary order for a certain arrangement.

If you go directly to point 1, you can start all over again, then when you get to the target state, you can find the desired state once, but if the title gives you a very backward state, it will cost a lot, which is a bit awkward.

So I was thinking about how to generate a full permutation in dictionary order when I did this.

Assuming that the state given at this time is 524 3 1, how can the next state be determined?From a human perspective, it is absolutely possible to start looking forward from the end of the sequence. For example, if you give a state of 12 3 4 5, it is easy to find that the next state should be 12 3 5 4, so a strategy is given. The first step should start looking forward from the end to the first pair of non-inverse ordinal numbers, which certainly makes sense, because if it is in reverse order,This means that case 1 must have already been exchanged, and it will never be the candidate for the next case. Therefore, the first non-inverse ordinal pair in 524 331 is 24, so the candidate for the exchange should be 2 (2 is the smaller one);Then continue thinking about which one to exchange with.First, it is clear that the subsequence 1 following 2 must be in reverse order.So if you want to swap with 2 and make the result the next in the dictionary order, then the number that you swap with 2 must be the smallest number greater than 2 after 2, so the second step is to look forward to the first number greater than 2 from the end of the sequence and swap with 2 (53,421 at this point), so the next step is also obvious.The sequence following 3 should be the one with the smallest dictionary order starting from 53, so the sequence following 3 should be inverted.Finally, you get the answer 53 1 2 4.

The process is not complicated, the order of thought and human thinking should be the same, directly to coding.

public void reverse(int []nums,int l,int r){
    while(l<r){
      int tmp=nums[l];
      nums[l]=nums[r];
      nums[r]=tmp;
      l++;
      r--;
    }
  }
  public void nextPermutation(int[] nums) {
    if(nums.length==0||nums.length==1) return;
    int i=nums.length-1;
    for(;i>=1;i--){
      if(nums[i]>nums[i-1])
        break;
    }
    if(i==0){
      Arrays.sort(nums);
      return;
    }
    int index=i-1;
    int diff=nums[i-1];
    for(i=nums.length-1;i>=0;i--){
      if(nums[i]>diff)
        break;
    }
    int tmp=nums[index];
    nums[index]=nums[i];
    nums[i]=tmp;
    reverse(nums,index+1,nums.length-1);
  }

summary