{"id":10914,"date":"2022-12-06T08:35:07","date_gmt":"2022-12-06T08:35:07","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=10914"},"modified":"2023-04-17T04:53:26","modified_gmt":"2023-04-17T04:53:26","slug":"next-permutation-and-previous-permutation-in-cpp","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/next-permutation-and-previous-permutation-in-cpp\/","title":{"rendered":"Previous Permutation and Next Permutation in C++"},"content":{"rendered":"

\"\"<\/p>\n

Permutations are popular topics in mathematics and computer science. In computer science, permutations are used to solve a wide range of problems, such as generating all possible combinations of a set of elements, sorting algorithms, and generating test cases for software. In this article, we will learn the ways to find the next and previous, and next permutation in C++ of the given arrangement approaches and code implementation of the previous and next permutation in C++.<\/p>\n

Previous and Next Permutation in C++<\/h2>\n

Given an array of numbers, rearrange the array such that the rearranged array becomes lexicographically next greater and previous smaller permutation of the initial given array.<\/p>\n

Examples of Next Greater Permutation<\/h3>\n
    \n
  1. [1,2,3] will have the next greater permutation [1,3,2].<\/li>\n
  2. [1,3,2] will have the next greater permutation [2,1,3].<\/li>\n
  3. [1,2,3,6,5,4] will have the next greater permutation [1,2,4,3,5,6].<\/li>\n<\/ol>\n

    Examples of Previous Smaller Permutation<\/h3>\n
      \n
    1. [3,2,1] will have the previous smaller permutation [3,1,2].<\/li>\n
    2. [3,1,2] will have the previous smaller permutation [2,3,1].<\/li>\n
    3. [1,9,4,6,7] will have the previous smaller permutation [1,7,4,6,9].<\/li>\n<\/ol>\n

      Brute Force Approach for finding Previous and Next Permutations in C++<\/h2>\n

      In this approach we will find all the possible arrangements of the given array and then we will find the arrangement which is smallest but greater than given arrangement as Next Greater Permutation and largest but smaller than given arrangement as Previous Smaller Permutation using recursion.<\/p>\n

      Time Complexity of Previous and Next Permutation in C++: O(N!XN)<\/strong><\/p>\n

      Where N is the number of elements in the given array.
      \nMaking the total number will require time complexity O(N!XN) and there will be a total N! Arrangement possible with the N number of elements so searching time will be O(N!).<\/p>\n

      Space Complexity of Previous and Next Permutation in C++: O(1).<\/strong><\/p>\n

      We don\u2019t require any additional space for this.<\/p>\n

      Next Permutation in C++ Using Inbuilt Function<\/h2>\n

      We can use the inbuilt function in C++ called next_permutation() which will directly return the lexicographically next greater permutation in C++.<\/p>\n

      Code for Next Permutation in C++ Using Inbuilt Function<\/h3>\n\t\t\t\t\t\t