{"id":16228,"date":"2023-05-10T07:44:37","date_gmt":"2023-05-10T07:44:37","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=16228"},"modified":"2023-05-10T07:44:37","modified_gmt":"2023-05-10T07:44:37","slug":"find-the-next-permutation-in-cpp","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/find-the-next-permutation-in-cpp\/","title":{"rendered":"Find the Next Permutation in C++"},"content":{"rendered":"

\"\"<\/p>\n

A permutation is defined as each of the numerous possible arrangements or orders that can be made for a set of objects or a group of objects. N! is used to represent it, where N is the range’s total number of elements. So, in this article, we will be discussing the next permutation in C++.<\/p>\n

What is the Next Permutation?<\/h2>\n

The next lexicographically superior permutation of an integer in an array is that integer’s next permutation. In more formal terms, if all of the array’s permutations are sorted in one container according to their lexicographical order, the permutation that follows it in the sorted container is the next permutation of that array. If this is not possible, the array must be rearranged in the smallest possible order (sorted ascending). <\/p>\n

As a result, there are two ways to solve this problem:<\/p>\n

    \n
  1. using in-built functions<\/li>\n
  2. without using in-built functions<\/li>\n<\/ol>\n

    So, let us discuss each of the methods to find the next permutation.<\/p>\n

    Method 1: Using in-built functions<\/h2>\n

    The C++ algorithm’s next_permutation() function is used to reorder the elements in the range [first, last] into the next lexicographically greater permutation. <\/p>\n

    Elements are compared with the operator in the first version and the given binary comparison function comp in the second. <\/p>\n

    Parameters Included<\/h3>\n

    There are three parameters to the next_permutation() function: <\/p>\n

      \n
    1. The first step is to create a bidirectional iterator that points to the first element in the range to be permuted.<\/li>\n
    2. Finally, an input iterator pointing one position beyond the range to be permuted is provided.<\/li>\n
    3. comp is a binary predicate function that takes two arguments and returns true if they are in the correct order; otherwise, it returns false. The elements are ordered using strict weak ordering.<\/li>\n<\/ol>\n

      Return Value of the Next Permutation Function<\/h3>\n

      If the function is able to reorder the object into lexicographically greater permutations, it returns true. Otherwise, the function returns false, indicating that the arrangement is not greater than the previous one, but rather the smallest possible (sorted in ascending order).<\/p>\n

      Time Complexity of the Next Permutation Function<\/h3>\n

      For half the distance between first and last, the time complexity reaches linear.<\/p>\n

      Code Implementation for Finding the Next Permutation<\/h3>\n\t\t\t\t\t\t