परमिटेशन्स लीटकोड सोल्यूशन  


अडचण पातळी मध्यम
वारंवार विचारले अडोब ऍमेझॉन सफरचंद Atlassian ब्लूमबर्ग बाइट डान्स हा कोड eBay फेसबुक गारेना GoDaddy गोल्डमन Sachs Google संलग्न मायक्रोसॉफ्ट ओरॅकल सेल्सबॉल्स सॅप उबेर व्हीएमवेअर वॉलमार्ट लॅब याहू
अल्गोरिदम बॅकट्रॅकिंग कोडिंग मुलाखत मुलाखतीची तयारी लेटकोड LeetCodeSolutions

प्यूमटेशन्स लीटकोड सोल्यूशन समस्येचा सोपा क्रम प्रदान करते आणि आम्हाला संपूर्ण वेक्टर परत करण्यास सांगते किंवा अॅरे दिलेल्या अनुक्रमातील सर्व क्रमांकाचे. तर, समस्येचे निराकरण करण्यापूर्वी आपण क्रमांकासह परिचित असले पाहिजे. तर, क्रमवार दिले जाणा given्या पूर्ण संख्येच्या व्यवस्थेशिवाय काही नाही. जेव्हा जेव्हा आपण म्हणतो की आपल्याला अनुक्रमांच्या सर्व क्रमांची आवश्यकता आहे. आमचा अर्थ असा आहे की दिलेल्या क्रमातील सर्व संभाव्य व्यवस्था आम्हाला मुद्रित करणे किंवा परत करणे आवश्यक आहे. चांगल्या प्रकारे समजून घेण्यासाठी काही उदाहरणे पहा.

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 मार्ग आहेत.

परमिटेशन्स लेटकोड सोल्यूशनसाठी बॅकट्रॅकिंग दृष्टीकोन  

परमिटेशन्स लीटकोड सोल्यूशनपिन

प्यूमटेशन्स लीटकोड सोल्यूशनने दिलेली समस्या आम्हाला दिलेल्या क्रमांकाचे सर्व क्रम निर्माण करण्यास सांगितले. साधारणपणे, आम्हाला एक क्रम निर्माण करणे आवश्यक आहे किंवा काही अनुक्रम पुनरावृत्ती जाण्याची गुरुकिल्ली आहे. परंतु येथे रिकर्सन किंवा बॅकट्रॅकिंग थोडा अवघड आहे. एक मार्ग म्हणजे अनपिक केलेल्या घटकांमधून एखादा घटक निवडणे आणि उत्तराच्या शेवटी ते ठेवणे. अशाप्रकारे एक क्रम निर्माण करा आणि हे निश्चित करा की हा क्रम बदलला गेला आहे आणि पुनरावृत्ती होऊ नये. परंतु हे करण्याऐवजी आम्ही कार्य करण्यासाठी एक सोपा मार्ग शोधण्याचा प्रयत्न करतो. जर आपण एखादा घटक निवडला आणि त्यास विद्यमान घटकासह स्वॅप करा. त्यानंतर चालू अनुक्रमणिकेनंतर अनुक्रम एक निर्देशांकासाठी सर्व क्रमवारी निर्माण करण्यासाठी रिकर्सिव कॉल करा.

हे सुद्धा पहा
दोन क्रमवारीबद्ध दुवा यादी विलीन करा

एकदा आम्ही क्रमवार पुढे तयार करण्यासाठी एक अनुक्रमणिका तयार करतो. आम्ही निवडलेला घटक काढून टाकतो आणि नंतर दुसरा घटक निवडतो आणि प्रक्रिया पुन्हा करतो. अशाप्रकारे आम्ही हे सुनिश्चित करतो की आम्ही प्रत्येक न वापरलेले घटक कमीतकमी एकदा सद्य स्थितीत ठेवल्या आहेत. आम्ही छोट्या सबप्रोब्लमला रिकर्सिव्ह कॉल केल्यामुळे. सध्याची अनुक्रमणिका नंतर सुरू होणार्‍या क्रमासाठी क्रम बदलण्यासाठी लहान सबप्रॉब्लम बनवित आहे. त्या क्रमवारीला सध्याच्या अनुक्रमेमध्ये जोडणे चालू अनुक्रमणिकेवरील घटकासह क्रमांकाचा संच पूर्ण करते. अशाप्रकारे आपण अ‍ॅरे डावीकडून उजवीकडे फिरवितो आणि समस्येस लहान सबप्रोब्लम्समध्ये विभाजित करतो. एकदा आम्ही आवश्यकतेपर्यंत पोहोचल्यावर आम्ही संभाव्य क्रमांकाची निर्मिती केली आणि आम्ही ती उत्तरेस जोडली.

बॅकट्रॅकिंग कोड  

परमिटेशन्स लेटकोड सोल्यूशनसाठी सी ++ कोड

#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]]

गुंतागुंत विश्लेषण  

वेळ कॉम्प्लेक्सिटी

ओ (सिग्मा (पी (एन, के)), जिथे पी किंवा के अर्धवट क्रमांकाचे के परमिट आहे. अधिक औपचारिकरित्या, पी (एन, के) = (एन!) / ((एनके)!).

हे सुद्धा पहा
उप-अ‍ॅरे लीटकोड सोल्यूशन उलट करून दोन अ‍ॅरे समान करा

स्पेस कॉम्प्लेक्सिटी

ओ (एन!), आम्हाला एन असलेले सर्व संभाव्य सोल्यूशन्स संग्रहित करायचे असल्याने! आकारात एन जेथे अ‍ॅरेचा आकार आहे.