Next Permutation LeetCode

nextPermutation.java

/*
n = 3

n! = n(n-1)!

3! = 6 permutari

1 2 3 
1 3 2  
2 1 3 
2 3 1 
3 1 2
3 2 1 

reverse(3 2 1) -> 1 2 3


1 2 7 4 5 6 3 --> nextPerm


1 2 9 4 5 6 7 8 3 -> nextPerm


5 4 3 2 1 0

reverse(5 4 3 2 1 0) , nu gaseste breakpoint = -1, face reverse de la 0 la n-1
        0         n-1 
 
Algoritmul lui Narayana Pandita

Step1:  Gaseste un pivot - prima crestere - breakpoint

Step2: Gaseste succesorul pivotului, adica cel mai mic element mai mare din dreapta

Step3: Swap(pivot, succesorul lui)

Step4: Inverseaza - reverse sufixul


abcd
1234

//1 2 5 4 3 -> nextPermutation(1 3 2 4 5)
*/

import java.util.*;

class Solution {
	
      public void nextPermutation(int[] nums) {

             int n = nums.length;//size

             int breakpoint = -1; //porninm cu pivot negativ


             //step 1 [1, 2, 3, 5, 4]
             //             i-1;i
             for(int i = n - 1; i > 0; i--) {

                 if(nums[i] > nums[i-1]) {

                      breakpoint = i - 1; //am gasit indicele pivotului
                      break;   //ne oprim                      
                 }
             }

             //daca nu avem breakpoint pivot
             if(breakpoint < 0) {
                 reverse(nums, 0, n - 1);
                 return;//nu mai continua urmatorii pasi din algoritm
             }

             //step3 ; gaseste succesorul pivotului
             ////step 1 [1, 2, 4, 5, 3]
             for(int i = n - 1; i >= breakpoint; i--) {
                     if(nums[i] > nums[breakpoint]) {
                          swap(nums, i, breakpoint);
                          break;
                     }
             }
        
             //step4 reverse suffix
             reverse(nums, breakpoint + 1, n - 1);//sufixul se extrage de la urmatorul indice breakpoint + 1 pana la final

             // 1 2 3 4 6 5 7 8 
             //         Breakpoint<----   


      }    

      private void reverse(int[] nums, int left, int right) {

                  while(left < right) {
                      swap(nums, left, right);
                      left++;
                      right--;
                  }
      }

      private void swap(int[] nums, int i, int j) {
          int temp = nums[i];
              nums[i] = nums[j];
              nums[j] = temp; 
      }


      public static void main(String[] args){
  
             Solution sol = new Solution();
             Scanner scanner = new Scanner(System.in);

             System.out.println("Numarul de elemente: ");
             int n = scanner.nextInt();
             int nums[] = new int[n];

             for(int i = 0; i < n; ++i) nums[i] = scanner.nextInt();

             System.out.println("Inainte: " + Arrays.toString(nums));
             sol.nextPermutation(nums);
             System.out.println("Next Permutation: " + Arrays.toString(nums));
       }
}

/*

                      permutare = 1 2 8  3 4 5 6 7
        Next Permutation: [1, 2, 8, 3, 4, 5, 6, 7]
        nextPermutare = 
*/