આગળ પરમ્યુટેશન


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન સફરજન બ્લૂમબર્ગ ByteDance ફેસબુક ફેક્ટસેટ ફ્લિપકાર્ટ Google માઈક્રોસોફ્ટ મોર્ગન સ્ટેન્લી Salesforce ઉબેર
શબ્દમાળા

હવે પછીની ક્રમચય સમસ્યામાં આપણે એક શબ્દ આપ્યો છે, તે શબ્દકોશના શબ્દકોશોના શબ્દકોશો શોધો.

ઉદાહરણ

input : str = "tutorialcup"
output : tutorialpcu

input : str = "nmhdgfecba"
output : nmheabcdfg

input : str = "algorithms"
output : algorithsm

input : str = "spoonfeed"
output : Next Permutation Doesnt exist

લેક્સિકોગ્રાફિકલ ઓર્ડર

કોઈ શબ્દના તમામ ક્રમચયો જ્યારે કોઈ ડિક્શનરીમાં ગોઠવે છે, ત્યારે શબ્દોનો ક્રમ પ્રાપ્ત થાય છે તેને શબ્દકોષ ક્રમ કહેવામાં આવે છે.

ભૂતપૂર્વ:

word = 'cat'
lexicographical order of permutations of 'cat' : 

act
atc
cat
cta
tac
tca

આપણે જોઈ શકીએ છીએ કે 'બિલાડી' એક્ટ કરતા વધારે લેક્સિકોગ્રાફિકલી વધારે છે.

નેક્સ્ટ પરમ્યુટેશન માટે એલ્ગોરિધમ

એક શબ્દ કે જે સંપૂર્ણપણે ઉતરતા ક્રમમાં ગોઠવવામાં આવે છે, ઉદાહરણ તરીકે: "nmhgfedcba" નો આગામી ક્રમચય નથી. અમે એવા શબ્દ માટે આગળનો ક્રમચય શોધી શકીએ જે ઉતરતા ક્રમમાં સંપૂર્ણપણે ગોઠવેલ નથી. ભૂતપૂર્વ: "nmhdgfecba". નીચે છે અલ્ગોરિધમનો:
આપેલ: str = “nmhdgfecba”

  1. શબ્દમાળાની જમણી બાજુથી પસાર થવું અને પ્રથમ પાત્રની શોધ કરો જે ઉતરતા ક્રમને અનુસરતું નથી. str માં 'd' ઉતરતા ક્રમને અનુસરતું નથી. 'd' = 3 ની અનુક્રમણિકા.
  2. 'ડી' ની જમણી બાજુએ, ASCII મૂલ્યમાં 'd' કરતા વધુ (અથવા નજીકના) પાત્રની શોધ કરો. [nmhd] gfecba માં 'e' 'd' કરતા વધારે છે. આ બાઈનરીસearchચ () ફંક્શનનો ઉપયોગ કરીને કરવામાં આવે છે.
  3. સ્વેપ 'e' અને 'd'. પરિણામી શબ્દમાળા "nmhegfdcba" છે.
  4. હવે પગલું 1 માં મળેલી અનુક્રમણિકા પછી પરિણામી શબ્દમાળાના ભાગને વિરુદ્ધ (વિપરીત () ફંક્શનનો ઉપયોગ કરીને કરવામાં આવે છે) રિવર્સ "gfdcba" ને વિરુદ્ધ કરો અને તેને ફરીથી મુખ્ય શબ્દમાળા પર જોડો.
  5. આઉટપુટ = “nmheabcdfg”, તે શબ્દકોશ છે “nmhgfedcba” ની હવે પછીની ક્રમચય.  આગળ પરમ્યુટેશન

આગળના અનુમતિ માટે અમલીકરણ

સી ++ પ્રોગ્રામ

#include <iostream> 
#include <bits/stdc++.h>
using namespace std; 

// function to reverse the string between index l and r
void reverse(string &str,int l,int r)
{
    while(l < r)
    swap(str[l++],str[r--]);
}

// function to search a character lying between index l and r 
// which is closest greater (just greater) than val
// and return it's index 
int binarySearch(string& str,int l,int r,char val) 
{ 
  int index = -1; 
  
  while (l <= r) 
  { 
    int mid = (l+r)/2;
    if (str[mid] <= val) 
    {
        r = mid - 1;
    }
    else 
    { 
      l = mid + 1; 
      if (index == -1 || str[index] >= str[mid]) 
        index = mid; 
    } 
  } 
  return index; 
} 

// this function generates next permutation (if there exists any such permutation) from the given string
// and returns True
// Else returns false
bool nextPermutation(string& str) 
{ 
  int len = str.length();
  int i = len-2; 
  
  while (i >= 0 && str[i] >= str[i+1]) 
  i--;
  
  if (i < 0) 
    return false; 
  else 
  { 
    int index = binarySearch(str,i+1,len-1,str[i]); 
    swap(str[i],str[index]); 
    reverse(str,i+1,len-1); 
    return true; 
  } 
} 

// main function to find next permutation
int main() 
{ 
  string str = "nmhdgfecba"; 
  bool is = nextPermutation(str); 
  
  if(is == false) 
    cout<< "Next Permutation Doesnt exist" <<endl; 
  else
    cout<<str<<endl; 
    
  return 0; 
} 
nmheabcdfg

જાવા પ્રોગ્રામ

class permutation
{
    // swap two characters of string 
    static void swap(StringBuilder sb,int l,int r)
    {
        char temp = sb.charAt(l);
        sb.setCharAt(l,sb.charAt(r));
        sb.setCharAt(r,temp);
    }
    
    // function to reverse the string between index l and r
    static void reverse(StringBuilder sb,int l,int r)
    {
        while(l < r)
        {
            swap(sb,l,r);
            l++;
            r--;
        }
    }
    
    // function to search a character lying between index l and r 
    // which is closest greater (just greater) than val
    // and return it's index 
    static int binarySearch(StringBuilder sb,int l,int r,char val) 
    { 
    	int index = -1; 
    	
    	while (l <= r) 
    	{ 
    		int mid = (l+r)/2;
    		if (sb.charAt(mid) <= val) 
    		{
    		    r = mid - 1;
    		}
    		else 
    		{ 
    			l = mid + 1; 
    			if (index == -1 || sb.charAt(index) >= sb.charAt(mid)) 
    				index = mid; 
    		} 
    	} 
    	return index; 
    } 
    
    // this function generates next permutation (if there exists any such permutation) from the given string
    // and returns True
    // Else returns false
    static boolean nextPermutation(StringBuilder sb) 
    { 
    	int len = sb.length();
    	int i = len-2; 
    	
    	while (i >= 0 && sb.charAt(i) >= sb.charAt(i+1)) 
    	i--;
    	
    	if (i < 0) 
    		return false; 
    	else 
    	{ 
    		int index = binarySearch(sb,i+1,len-1,sb.charAt(i)); 
    		swap(sb,i,index); 
    		reverse(sb,i+1,len-1); 
    		return true; 
    	} 
    }    
    
    // main function to find next permutation
    public static void main(String args[])
    {
        String str = "nmhdgfecba";
        // strings in java are immutable,so we convert strings into StringBuilder
        // StringBuilder are mutable strings        
        StringBuilder sb = new StringBuilder(str);

    	boolean is = nextPermutation(sb); 
    	
    	if(is == false) 
    		System.out.println("Next Permutation Doesnt exist"); 
    	else
    		System.out.println(sb);
           
    }
}
nmheabcdfg

એસટીએલ લાઇબ્રેરીનો ઉપયોગ કરીને આગળ પરમ્યુટેશન

ની એસટીએલ લાઇબ્રેરી સી ++ ફંક્શન નેક્સ્ટ_પાર્મ્યુટેશન () સમાવે છે જે આપેલ સ્ટ્રિંગના આગળના ક્રમચય બનાવે છે

#include <iostream>
#include <bits/stdc++.h>    // STL library of C++
using namespace std;

int main() 
{
    string str = "nmhdgfecba";
    
    // next_permutation() is present in STL library
    // next_permutation() generates Next Permutation of a string if it exists
    // and returns true
    // else returns false
    if(next_permutation(str.begin(),str.end()))
    cout<<str<<endl;
    else
    cout<<"Next Permutation Doesnt exist";

    return 0;
}
nmheabcdfg

જટિલતા વિશ્લેષણ

  1. સમય જટિલતા: એકંદરે સમય જટિલતા T (n) = O (n)
    • સૌથી ખરાબ કિસ્સામાં, આગલા પ્રગટનું પ્રથમ પગલું () ઓ (એન) સમય લે છે.
    • દ્વિસંગી શોધ () ઓ (લnગિન) સમય લે છે.
    • વિપરીત () ઓ (n) સમય લે છે.
  2. અવકાશ જટિલતા: એ (એન) = ઓ (1) કારણ કે અહીં આપણે કાર્યની ગણતરી દરમિયાન કોઈ સહાયક જગ્યાનો ઉપયોગ કરતા નથી. આનો અર્થ એ છે કે આગળની ક્રમચય સમસ્યાની અવકાશ જટિલતા, આ કિસ્સામાં, સતત છે.

સંદર્ભ