Next permutation function in python

Suppose we want to implement the next permutation method, that method rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, this method will rearrange it as the lowest possible order (That is actually, sorted in ascending order). The replacement must be in-place and do not use any extra memory. For example, if the Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Let us see the steps −

• found := false, i := length of the array – 2
• while i >= 0
  • if A[i] < A[i + 1], then found := True, and terminate the loop
  • increase i by 1
• if found := false, then sort the array A,
• otherwise
  • m := find maximum element index from index i + 1, from A, and from the current element A[i]
  • swap the elements A[i] and A[m]
  • reverse all the elements from i+1 to the end in A

Let us see the following implementation to get better understanding −

Example

 Live Demo

class Solution(object):
   def nextPermutation(self, nums):
      found = False
      i = len(nums)-2
      while i >=0:
         if nums[i] < nums[i+1]:
            found =True
            break
         i-=1
      if not found:
         nums.sort()
      else:
         m = self.findMaxIndex(i+1,nums,nums[i])
         nums[i],nums[m] = nums[m],nums[i]
         nums[i+1:] = nums[i+1:][::-1]
      return nums
   def findMaxIndex(self,index,a,curr):
      ans = -1
      index = 0
      for i in range(index,len(a)):
         if a[i]>curr:
            if ans == -1:
               ans = curr
               index = i
            else:
               ans = min(ans,a[i])
               index = i
      return index
ob1 = Solution()
print(ob1.nextPermutation([1,2,5,4,3]))

Input

[1,2,5,4,3]

Output

[1, 3, 2, 4, 5]

Updated on 04-May-2020 05:42:40

• Related Questions & Answers
• Lexicographically next permutation in C++
• Program to get next integer permutation of a number in C++
• Permutation and Combination in Python?
• Previous Permutation With One Swap in Python
• Program to find next state of next cell matrix state in Python?
• Generate all permutation of a set in Python?
• Program to find decode XORed permutation in Python
• Python Program for BogoSort or Permutation Sort
• Find next sibling element in Selenium, Python?
• Permutation Sequence in C++
• Find Permutation in C++
• Permutation in String in C++
• Interesting Python Implementation for Next Greater Elements
• Python program for permutation of a given string inbuilt function in python
• Find n-th lexicographically permutation of a strings in Python

The algorithm is implemented in module more_itertools as part of function more_itertools.distinct_permutations:

• Documentation;
• Source code.

def next_permutation(A):
            # Find the largest index i such that A[i] < A[i + 1]
            for i in range(size - 2, -1, -1):
                if A[i] < A[i + 1]:
                    break
            #  If no such index exists, this permutation is the last one
            else:
                return

            # Find the largest index j greater than j such that A[i] < A[j]
            for j in range(size - 1, i, -1):
                if A[i] < A[j]:
                    break

            # Swap the value of A[i] with that of A[j], then reverse the
            # sequence from A[i + 1] to form the new permutation
            A[i], A[j] = A[j], A[i]
            A[i + 1 :] = A[: i - size : -1]  # A[i + 1:][::-1]

Alternatively, if the sequence is guaranteed to contain only distinct elements, then next_permutation can be implemented using functions from module more_itertools:

import more_itertools

# raises IndexError if s is already the last permutation
def next_permutation(s):
   seq = sorted(s)
   n = more_itertools.permutation_index(s, seq)
   return more_itertools.nth_permutation(seq, len(seq), n+1)

How do you generate the next permutation in Python?

What is next permutation function?

Is there a permutation function in Python?