31. Next Permutation

Problem Statement

Pattern: Next Permutation

---

Solution

public static void swap(int[] x, int a, int b) {
	int t = x[a];
	x[a] = x[b];
	x[b] = t;
}
 
 
public void nextPermutation(int[] nums){
	if (nums.length == 1) return;
	
	// pivot -> first smaller el in reverse, el right before the decreasing suffix
	int pivot = findPivot(nums);
	
	if(pivot != -1) {
		// nextPivot -> rightmost-element > pivot
		int nextPivot = findNextPivot(nums, nums[pivot]);
		// swap with pivot
		swap(nums, pivot, nextPivot);
	}
	// sort decreasing suffix to ascending
	Arrays.sort(nums, pivot+1, nums.length);
}
 
private int findNextPivot(int[] nums, int pivotElement) {
	// npi -> next pivot index
	// return index of first element > pivotElement in reverse
	for (int npi = nums.length-1; npi >= 0; npi--)
		if(nums[npi] > pivotElement) return npi;
	return -1;
}
 
private int findPivot(int[] nums) {
	// return first non-increasing element in reverse
	for(int pivot = nums.length-1; pivot >= 0 ; pivot--)
		if(pivot < nums.length-1 && nums[pivot] < nums[pivot+1])
			return pivot;
	return -1;
}

Notes