પરમ્યુટેશન લીટકોડ સોલ્યુશન


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન સફરજન Atlassian બ્લૂમબર્ગ ByteDance ઇબે ફેસબુક ગરેના GoDaddy ગોલ્ડમૅન સૅશ Google LinkedIn માઈક્રોસોફ્ટ ઓરેકલ Salesforce એસએપી ઉબેર વીએમવેર વોલમાર્ટ લેબ્સ યાહૂ
બેકટ્રેકીંગ

પ્રોમ્યુટેશન લીટકોડ સોલ્યુશન સમસ્યા પૂર્ણાંકોનો એક સરળ ક્રમ પૂરો પાડે છે અને અમને સંપૂર્ણ વેક્ટર પરત કરવા માટે કહે છે અથવા એરે આપેલ ક્રમના તમામ ક્રમચયોની. તેથી, સમસ્યા હલ કરતા પહેલા. આપણે ક્રમચયોથી પરિચિત હોવા જોઈએ. તેથી, ક્રમચય એ આપેલ પૂર્ણાંકોની ગોઠવણી સિવાય કંઈ નથી. તેથી, જ્યારે આપણે કહીએ કે આપણને ક્રમના બધા ક્રમચયોની જરૂર છે. અમારું અર્થ એ છે કે આપેલ અનુક્રમની બધી સંભવિત વ્યવસ્થાઓને છાપવા અથવા પાછા આપવી પડશે. ચાલો સારી સમજ માટે થોડા ઉદાહરણો પર એક નજર કરીએ.

Given sequence: [1,2,3]
Permutations: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

સમજૂતી: તમે અનુક્રમમાં 1, 2, 3 લખી શકો છો તે બધી રીતો આઉટપુટ તરીકે આપવામાં આવી છે. ક્રમચયમાં 6, 1, 2 લખવાની કુલ 3 રીત છે.

[0,1]
[[0,1],[1,0]]

સમજૂતી: 2, 0 લખવા માટે ફક્ત 1 રસ્તાઓ છે.

પરમ્યુટેશન લીટકોડ સોલ્યુશન માટે બેકટ્રેકિંગ અભિગમ

પરમ્યુટેશન લીટકોડ સોલ્યુશન

પ્રોમ્યુટેશન્સ લીટકોડ સોલ્યુશનની સમસ્યા અમને આપેલા ક્રમના તમામ ક્રમચયો બનાવવા માટે કહે છે. સામાન્ય રીતે, આપણે ક્રમચય ઉત્પન્ન કરવું જરૂરી છે અથવા કેટલીક અનુક્રમ રિકર્ઝન એ જવાની ચાવી છે. પરંતુ અહીં રિકર્ઝન અથવા બેકટ્રેકીંગ થોડી મુશ્કેલ છે. એક રીત અનપિકડ તત્વોમાંથી કોઈ ઘટક પસંદ કરી અને તેને જવાબના અંતે મૂકીને હોઈ શકે છે. આ રીતે ક્રમચય ઉત્પન્ન થાય છે અને કોઈક યાદ રાખવાની ખાતરી કરો કે આ ક્રમચય ઉત્પન્ન થયો છે અને પુનરાવર્તિત થવો જોઈએ નહીં. પરંતુ આ કરવાને બદલે, અમે કાર્ય કરવા માટેનો એક સરળ રસ્તો શોધવાનો પ્રયાસ કરીએ છીએ. શું જો આપણે કોઈ તત્વ પસંદ કરીએ અને તેને વર્તમાન તત્વ સાથે અદલાબદલ કરીએ. પછી વર્તમાન અનુક્રમણિકા પછી ક્રમ એક અનુક્રમણિકા માટેના બધા ક્રમચયને ઉત્પન્ન કરવા માટે રિકરિવ કiveલ કરો.

એકવાર અમે ક્રમચયો એક અનુક્રમણિકા આગળ બનાવવા સાથે કરવામાં આવે છે. અમે ચૂંટેલા તત્વને દૂર કરીએ છીએ, અને પછી બીજું તત્વ પસંદ કરીએ છીએ અને પ્રક્રિયાને પુનરાવર્તિત કરીએ છીએ. આ રીતે અમે ખાતરી કરીએ છીએ કે અમે દરેક ન વપરાયેલ તત્વને વર્તમાન સ્થિતિમાં ઓછામાં ઓછા એક વખત મૂક્યા છે. અને કારણ કે અમે નાના પેટા પ્રોબ્લેમ પર રિકરિવ ક callલ કર્યો છે. નાનો સબપ્રોબ્લમ વર્તમાન અનુક્રમણિકા પછી શરૂ થતાં ક્રમ માટે ક્રમચય ઉત્પન્ન કરે છે. તે ક્રમ્યુટેશન્સને વર્તમાન ક્રમચયમાં ઉમેરવું એ વર્તમાન અનુક્રમણિકામાં સેટ કરેલા તત્વ સાથે ક્રમચયનો સમૂહ પૂર્ણ કરે છે. આ રીતે આપણે એરેને ડાબેથી જમણે ખસેડતા રહીએ છીએ અને સમસ્યાને નાના પેટા પ્રોબ્લેમ્સમાં વહેંચીએ છીએ. એકવાર અમે જરૂરિયાત પર પહોંચ્યા પછી અમે શક્ય સંમિશ્રણ ઉત્પન્ન કર્યું અને અમે તેને જવાબમાં ઉમેરીશું.

બેકટ્રેકીંગ કોડ

પરમ્યુટેશન લીટકોડ સોલ્યુશન માટે સી ++ કોડ

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

void permutationUtil(vector<int> &nums, int i, int &numsSize, vector<vector<int>> &answer){
    if(i == numsSize){
        answer.push_back(nums);
    }
    for(int j = i; j < numsSize; j++){
        swap(nums[i], nums[j]);
        permutationUtil(nums, i+1, numsSize, answer);
        swap(nums[i], nums[j]);
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> answer;
    int numsSize = nums.size();
    permutationUtil(nums, 0, numsSize, answer);
    return answer;
}

int main(){
    vector<int> nums({1, 2, 3});
    vector<vector<int>> answer = permute(nums);
    for(auto i: answer){
        for(auto j: i)
            cout<<j<<" ";
        cout<<"\t";
    }
}
1 2 3   1 3 2   2 1 3   2 3 1   3 2 1   3 1 2

પરમ્યુટેશન લીટકોડ સોલ્યુશન માટે જાવા કોડ

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main {
    public static void permutationUtil(List<Integer> nums, int i, int numsSize, List<List<Integer>> answer){
        if(i == numsSize){
            answer.add(new ArrayList<Integer>(nums));
        }
        for(int j = i; j < numsSize; j++){
            Collections.swap(nums, i, j);
            permutationUtil(nums, i+1, numsSize, answer);
            Collections.swap(nums, i, j);
        }
    }
 
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> answer = new LinkedList();
        int numsSize = nums.length;
        List<Integer> list = new ArrayList<Integer>();
        for(int i=0;i<numsSize;i++)
            list.add(nums[i]);
        permutationUtil(list, 0, numsSize, answer);
        return answer;
    }
 
    public static void main(String[] args){
    	int nums[] = {1, 2, 3};
    	List<List<Integer>> answer = permute(nums);
    	System.out.println(answer.toString());
    }
}
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]

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

સમય જટિલતા

ઓ (સિગ્મા (પી (એન, કે)), જ્યાં પી એ કે આંશિક ક્રમચયનું કે ક્રમચય છે. વધુ lyપચારિક રીતે, પી (એન, કે) = (એન!) / ((એનકે)!).

અવકાશ જટિલતા

ઓ (એન!), કારણ કે આપણે બધા સંભવિત ઉકેલો સંગ્રહવા પડશે જે એન છે! કદમાં જ્યાં એન એરેનું કદ છે.