Brute Force Approach

Method 2: Optimal Approach

As a brute force approach, we can generate all the possible permutations of the given array and store all the generated sequences. Then we sort all these arrays in increasing order and find the lexicographically next permutation by a simple searching technique.

Algorithm:

Create a recursive function called permute that generates all the possible permutations of the given array by swapping the elements.
Keep storing the generated combinations in another array named as total.
Then iterate through this array and compare each one to the input array to find a match.
Use JSON.stringify to compare the arrays.
Once we find our input array, just return the next array in the traversal which will be our lexicographically next permutation.
In a case, if there is no such permutation, we print a message that states no permutation possible.

Example: Below is the implementation of the above approach

Javascript

// JavaScript code for the above approach 
  
// Recursive function to generate all permutations  
const permute = (arr, idx, res) => { 
  
    // Base case 
    if (idx === arr.length - 1) { 
        res.push([...arr]); 
        return; 
    } 
  
    const n = arr.length; 
  
    // Iterate the array starting from the new index 
    for (let i = idx; i < n; i++) { 
      
        // Swap the elements 
        [arr[idx], arr[i]] = [arr[i], arr[idx]]; 
          
        // Make a recursive call  
        permute(arr, idx + 1, res); 
          
        // Backtrack 
        [arr[idx], arr[i]] = [arr[i], arr[idx]]; 
    } 
}; 
  
// Function to call the recursive function 
function generatePermutations(arr) { 
    const res = []; 
    permute(arr, 0, res); 
    return res; 
} 
  
// Input 
let arr = [1, 2, 3]; 
let total = generatePermutations(arr); 
  
const n = total.length; 
  
// Sort the permutations' array 
total.sort(); 
  
let ans = null; 
  
// Check if the input array is  
// the largest possible permutation 
if (JSON.stringify(total[n - 1]) ===  
        JSON.stringify(arr)) { 
          
    // If yes, then the next permutation  
    // is the smallest permutation 
    ans = total[0]; 
} 
  
// Find the next permutation 
for (let i = 0; i < n - 1; i++) { 
    if (JSON.stringify(total[i]) ===  
            JSON.stringify(arr)) { 
        ans = total[i + 1]; 
        break; 
    } 
} 
  
// Print the answer 
if (ans) { 
    console.log(ans); 
} 
else { 
    console.log("No next permutation found"); 
}

Output

[ 1, 3, 2 ]

Time Complexity: O(N!*N)

Space Complexity: O(1)

JavaScript Program to Find Lexicographically Next Permutation

Given an array of distinct integers, we want to find the lexicographically next permutation of those elements. In simple words, when all the possible permutations of an array are placed in a sorted order, it is the lexicographic order of those permutations. In this case, we have to find the next greater permutation of the elements in this sorted or lexicographic order.

Examples:

Example 1:
Input: [1, 2, 3]
Output: [1, 3, 2]
Explanation:  If all the permutations of these elements are arranged in a sorted order:
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]
Here, next greater permutation of [1, 2, 3] is [1, 3, 2].

Example 2:
Input: [6, 3, 4, 7, 1]
Output: [6, 3, 7, 1, 4]
Explanation: If all the permutations of these elements are arranged in a sorted order, 
next greater permutation of  [6, 3, 4, 7, 1] is [6, 3, 7, 1, 4].

Table of Content

Brute Force Approach
Optimal Approach

Tags:

#Geeks Premier League 2023 #JavaScript-DSA #JavaScript-Program #Geeks Premier League #JavaScript #Web Technologies