Next Permutation in C++, Java, Python

The goal is to print the lexicographically next bigger permutation of an n-sized array arr[]. If no further permutation exists, then determine the lexicographically lowest permutation of the particular array.

Let us better grasp the issue by first writing all permutations of [1, 2, 4] in lexicographical sequence.

[1, 2, 4]; [1, 4, 2], [2, 1, 4], [2, 4, 1], [4, 1, 2] and [4, 2, 1]

Should we provide any of the above—except from the last—as input, we must then determine the next one in order. Should we provide last as input, we must revert to the first one.

Examples

Input: arr = [2, 4, 1, 7, 5, 0]
Output: [2, 4, 5, 0, 1, 7]
Explanation: The next permutation of the given array is 2 4 5 0 1 7


Input: arr = {3, 2, 1]
Output: [1, 2, 3]
Explanation: As arr[] is the last permutation. So, the next permutation is the lowest one.

[Naive Approach] Generating All Permutations – O(n!*n*log(n!)) Time and O(n!) Space

Our first basic thought is that we would first create and sort all potential permutations of a particular array. Once arranged, we find the current permutation in this list. The next permutation is just the subsequent arrangement in the sorted sequence. Show the first permutation—the smallest permutation—should the present arrangement be the last in the list.

Note: This method will only be effective in an input array free of duplicate values. Please see the expected method to manage duplicates here.

C++

// C++ Program to find the next permutation by generating 
// all permutations

#include <bits/stdc++.h>
using namespace std;

// Generates all permutations
void permutations(vector<vector<int>>& res, vector<int>& curr, 
                  int idx);

// Function to get the next permutation
void nextPermutation(vector<int>& arr) {
  
    // Generate all permutations and store in res
    vector<vector<int>> res;
    permutations(res, arr, 0);
    sort(res.begin(), res.end());

    // Traverse through res and find the next permutation
    for (int i = 0; i < res.size(); i++) {
      
        // Found a match
        if (res[i] == arr) {
          
            // Store the next
            if (i < res.size() - 1)
                arr = res[i + 1];
          
            // If the given permutation is the last
            if (i == res.size() - 1)
                arr = res[0];
          
            break;
        }
    }
}

// Function to generate all possible permutations
void permutations(vector<vector<int>>& res, vector<int>& arr, 
                  int idx) {
  
    // Base case: if idx reaches the end of the array
    if (idx == arr.size() - 1) {
        res.push_back(arr);
        return;
    }

    // Permutations made by swapping each element
    // starting from index `idx`
    for (int i = idx; i < arr.size(); i++) {
      
        // Swapping
        swap(arr[idx], arr[i]);

        // Recursive call to create permutations
        // for the next element
        permutations(res, arr, idx + 1);

        // Backtracking
        swap(arr[idx], arr[i]);
    }
}

int main() {
    vector<int> arr = { 2, 4, 1, 7, 5, 0 };
    nextPermutation(arr);
  
      for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    
    return 0;
}

Java

// Java Program to find the next permutation by generating 
// all permutations

import java.util.*;

class GfG {
  
    // Find next permutation
    static void nextPermutation(int[] arr) {
        List<int[]> res = new ArrayList<>();

        permutations(res, arr, 0);
        Collections.sort(res, Arrays::compare);
      
        // Traverse to find next permutation
        for (int i = 0; i < res.size(); i++) {
          
            // Found a match
            if (Arrays.equals(res.get(i), arr)) {
              
                // Store the next in arr
                if (i < res.size() - 1) {
                    int[] nextPerm = res.get(i + 1);
                    for(int j = 0; j < arr.length; j++)
                        arr[j] = nextPerm[j];
                }
              
                // If the given permutation is the last
                if (i == res.size() - 1) {
                    int[] nextPerm = res.get(0);
                    for(int j = 0; j < arr.length; j++)
                        arr[j] = nextPerm[j];
                }
                
                break;
            }
        }
    }

    // Generate permutations recursively
    static void permutations(List<int[]> res, int[] arr, int idx) {
      
        // Base case: if idx reaches the end of the array
        if (idx == arr.length - 1) {
            res.add(arr.clone());
            return;
        }
      
        // Permutations made by swapping each element
        // starting from index `idx`
        for (int i = idx; i < arr.length; i++) {
          
            // Swapping
            swap(arr, idx, i);
          
            // Recursive call to create permutations
            // for the next element
            permutations(res, arr, idx + 1);
          
            // Backtracking
            swap(arr, idx, i);  
        }
    }
  
    // Swap function
    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    } 

    public static void main(String[] args) {
        int[] arr = {2, 4, 1, 7, 5, 0};  
        nextPermutation(arr);
        
        for (int num : arr)
            System.out.print(num + " ");
    }
}

Python

# Python Program to find the next permutation by generating 
# all permutations

# Generates all permutations
def permutations(res, arr, idx):
    
    # Base case: if idx reaches the end of the list
    if idx == len(arr) - 1:
        res.append(arr[:])
        return

    # Generate permutations by swapping each
    # element starting from index `idx`
    for i in range(idx, len(arr)):
        
        # Swapping
        arr[idx], arr[i] = arr[i], arr[idx]

        # Recursive call to create permutations 
        # for the next element
        permutations(res, arr, idx + 1)

        # Backtracking
        arr[idx], arr[i] = arr[i], arr[idx]


def next_permutation(arr):
    
    # Begin with the smallest permutation
    curr = arr[:]

    # Generate all permutations and store in res
    res = []
    permutations(res, curr, 0)
    res.sort()

    # Traverse through res and print the next permutation
    for i in range(len(res)):
        
        # Found a match
        if res[i] == arr:
            
            # Print next
            if i < len(res) - 1:
                arr[:] = res[i + 1]
                
            else:
                
                # If the given permutation is 
                # the last
                arr[:] = res[0]
            
            break


if __name__ == "__main__":
    arr = [2, 4, 1, 7, 5, 0]
    next_permutation(arr)
    print(" ".join(map(str, arr)))

Output

2 4 5 0 1 7 

Time Complexity: O(n!nlog(n!). n is the total number of elements in the input sequence, so reflecting all conceivable permutation.
Auxiliary Space: O(n!). Permutation storage

[Expected Approach] Generating Only Next – O(n) Time and O(1) Space

[1, 2, 3, 4, 5]: next is [1, 2, 3, 5, 4]  
Observation: 4 moves and 5 comes in place of it


[1, 2, 3, 5, 4]: next is [1, 2, 4, 3, 5] 
Observation: 3 moves, 4 comes in place of it. 3 comes before 5 (mainly 3 and 5 are in sorted order)


[1, 2, 3, 6, 5, 4]: next is [1, 2, 4, 3, 5, 6] 
Observation: 3 moves, 4 comes in place of it. [3, 5 and 6 are placed in sorted order]


[3, 2, 1]: next is [1, 2, 3]
Observation: All elements are reverse sorted. Result is whole array sorted.


[1, 2, 3, 6, 4, 5]: next is [1, 2, 3, 6, 5, 4] 
Observation: 4 moves and 5 comes in place of it

Notes on the next permutation:

• Changing the number in a spot as right as feasible helps us to obtain the following permutation.
• The rightmost number smaller than its next comes first for movement.
• On the right side of the pivot, the rightmost bigger number will determine the number to come in-place.
• Except from the very first, every permutation has a growing suffix. We will thus acquire the next bigger permutation if we shift the pattern from the pivot point—where the growing suffix breaks—to its next feasible lexicographic representation.

Apply the above observation by following the guidelines below:

• From end, iterate across the provided array looking for the first index (pivot) that does not follow property of non-increasing suffix, i.e, arr[i] < arr[i + 1].
• Should pivot index not exist, the provided sequence in the array is the maximum feasible. Then flip the whole array. The result for [3, 2, 1] for instance would be [1, 2, 3].
• Otherwise, start iteratively from the end and locate in suffix the successor (rightmost bigger element) of pivot.
• Revers the pivot and successor.
• Reversing the array from pivot + 1 till n will minimize the suffix component.

C++

// C++ Program to find the next permutation by 
// generating only next

#include <bits/stdc++.h>
using namespace std;

void nextPermutation(vector<int> &arr) {
  
    int n = arr.size(); 

     // Find the pivot index
    int pivot = -1; 
    for (int i = n - 2; i >= 0; i--) {
        if (arr[i] < arr[i + 1]) {
            pivot = i;
            break;
        }
    }

    // If pivot point does not exist, reverse the
    // whole array
    if (pivot == -1) {
        reverse(arr.begin(), arr.end());
        return;
    }

    // find the element from the right that
    // is greater than pivot
    for (int i = n - 1; i > pivot; i--) {
        if (arr[i] > arr[pivot]) {
            swap(arr[i], arr[pivot]);
            break;
        }
    }

    // Reverse the elements from pivot + 1 to the 
    // end to get the next permutation
    reverse(arr.begin() + pivot + 1, arr.end());
}

int main()
{
    vector<int> arr = { 2, 4, 1, 7, 5, 0 };
    nextPermutation(arr);    
    for (int x : arr) 
        cout << x << " ";    
    return 0;
}

C

// C Program to find the next permutation by 
// generating only next

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void reverse(int arr[], int start, int end) {
    while (start < end) {
        swap(&arr[start], &arr[end]);
        start++;
        end--;
    }
}

void nextPermutation(int *arr, int n) {
  
    // Find the pivot index
    int pivot = -1;
    for (int i = n - 2; i >= 0; i--) {
        if (arr[i] < arr[i + 1]) {
            pivot = i;
            break;
        }
    }

    // If pivot point does not exist, 
    // reverse the whole array
    if (pivot == -1) {
        reverse(arr, 0, n - 1);
        return;
    }

    // Find the element from the right that
    // is greater than pivot
    for (int i = n - 1; i > pivot; i--) {
        if (arr[i] > arr[pivot]) {
            swap(&arr[i], &arr[pivot]);
            break;
        }
    }

    // Reverse the elements from pivot + 1 to the end
    reverse(arr, pivot + 1, n - 1);
}

int main() {
    int arr[] = { 2, 4, 1, 7, 5, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);

    nextPermutation(arr, n);

    // Print the result
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Java

// Java Program to find the next permutation by 
// generating only next

import java.util.Arrays;

class GfG {
    static void nextPermutation(int[] arr) {
        int n = arr.length;

        // Find the pivot index
        int pivot = -1;
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] < arr[i + 1]) {
                pivot = i;
                break;
            }
        }

        // If pivot point does not exist, reverse the whole array
        if (pivot == -1) {
            reverse(arr, 0, n - 1);
            return ;
        }

        // Find the element from the right that is greater than pivot
        for (int i = n - 1; i > pivot; i--) {
            if (arr[i] > arr[pivot]) {
                swap(arr, i, pivot);
                break;
            }
        }

        // Reverse the elements from pivot + 1 to the end
        reverse(arr, pivot + 1, n - 1);
    }

    // Helper method to reverse array
    private static void reverse(int[] arr, int start, int end) {
        while (start < end) {
            swap(arr, start++, end--);
        }
    }

    // Helper method to swap two elements
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = { 2, 4, 1, 7, 5, 0 };
        nextPermutation(arr);
        
        for(int i = 0; i < arr.length; i++)
        System.out.print(arr[i] + " ");
    }
}

Python

# Python Program to find the next permutation by 
# generating only next

def next_permutation(arr):
    n = len(arr)
    
    # Find the pivot index
    pivot = -1
    for i in range(n - 2, -1, -1):
        if arr[i] < arr[i + 1]:
            pivot = i
            break
    
    # If pivot point does not exist, 
    # reverse the whole array
    if pivot == -1:
        arr.reverse()
        return

    # Find the element from the right 
    # that is greater than pivot
    for i in range(n - 1, pivot, -1):
        if arr[i] > arr[pivot]:
            arr[i], arr[pivot] = arr[pivot], arr[i]
            break

    # Reverse the elements from pivot + 1 to the end in place
    left, right = pivot + 1, n - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1


arr = [ 2, 4, 1, 7, 5, 0 ]
next_permutation(arr)
print(" ".join(map(str, arr)))

C#

// C# Program to find the next permutation by 
// generating only next

using System;

class GfG {
    static void NextPermutation(int[] arr) {
        int n = arr.Length;

        // Find the pivot index
        int pivot = -1;
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] < arr[i + 1]) {
                pivot = i;
                break;
            }
        }

        // If pivot point does not exist, reverse the
        // whole array
        if (pivot == -1) {
            Array.Reverse(arr);
            return;
        }

        // Find the element from the right that
        // is greater than pivot
        for (int i = n - 1; i > pivot; i--) {
            if (arr[i] > arr[pivot]) {
                int temp = arr[i];
                arr[i] = arr[pivot];
                arr[pivot] = temp;
                break;
            }
        }

        // Reverse the elements from pivot + 1 to the 
        // end to get the next permutation
        Array.Reverse(arr, pivot + 1, n - pivot - 1);
    }

    static void Main() {
        int[] arr = { 2, 4, 1, 7, 5, 0 };
        NextPermutation(arr);
        foreach (int x in arr) {
            Console.Write(x + " ");
        }
    }
}

JavaScript

// JavaScript Program to find the next permutation by 
// generating only next

function nextPermutation(arr) {
    const n = arr.length; 

    // Find the pivot index
    let pivot = -1; 
    for (let i = n - 2; i >= 0; i--) {
        if (arr[i] < arr[i + 1]) {
            pivot = i;
            break;
        }
    }

    // If pivot point does not exist, reverse the
    // whole array
    if (pivot === -1) {
        arr.reverse();
        return;
    }

    // find the element from the right that
    // is greater than pivot
    for (let i = n - 1; i > pivot; i--) {
        if (arr[i] > arr[pivot]) {
            [arr[i], arr[pivot]] = [arr[pivot], arr[i]];
            break;
        }
    }

    // Reverse the elements from pivot + 1 to the 
    // end to get the next permutation in place
    let left = pivot + 1;
    let right = n - 1;
    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
    }
}

const arr = [2, 4, 1, 7, 5, 0];
nextPermutation(arr);    
console.log(arr.join(" "));