next_permutation c++ implementation code example

Example 1: java next_permutation

public static boolean next_permutation(int[] arr) {
	int len = arr.length;
	int i = len - 1;

    // 1. find largest i where arr[i - 1] < arr[i]
	while (i > 0) {
		if (arr[i - 1] < arr[i]) break;
    	i--;
  	}

  	if (i <= 0) return false;

  	// 2. find largest j where arr[i - 1] < arr[j] and j >= i
  	int j = len - 1;
  	while (j >= i) {
    	if (arr[i - 1] < arr[j]) break;
    	j--;
  	}

	// 3. swap elements between arr[i-1] and arr[j]
  	swap(i - 1, j, arr);

  	// 4. reverse elements from i to end of array
  	len--;
  	while (i < len) {
    	swap(i, len, arr);
    	len--;
    	i++;
  	}
  	return true;
}

public static void swap(int x, int y, int[] arr) {
  	int temp = arr[x];
  	arr[x] = arr[y];
  	arr[y] = temp;
}

Example 2: how next_permutation works in c++

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
Swap a[k] with a[l].
Reverse the sequence from a[k + 1] up to and including the final element a[n].
  
For example, given the sequence [1, 2, 3, 4] (which is in increasing order), and given that the index is zero-based, the steps are as follows:

Index k = 2, because 3 is placed at an index that satisfies condition of being the largest index that is still less than a[k + 1] which is 4.
Index l = 3, because 4 is the only value in the sequence that is greater than 3 in order to satisfy the condition a[k] < a[l].
The values of a[2] and a[3] are swapped to form the new sequence [1,2,4,3].
The sequence after k-index a[2] to the final element is reversed. Because only one value lies after this index (the 3), the sequence remains unchanged in this instance. Thus the lexicographic successor of the initial state is permuted: [1,2,4,3].
Following this algorithm, the next lexicographic permutation will be [1,3,2,4], and the 24th permutation will be [4,3,2,1] at which point a[k] < a[k + 1] does not exist, indicating that this is the last permutation.