परम्युटेसन लेटकोड समाधान


कठिनाई तह मध्यम
बारम्बार सोधिन्छ एडोब अमेजन एप्पल Atlassian ब्लूमबर्ग बाइटडेन्स eBay फेसबुक Garena GoDaddy Goldman सैक्स गुगल LinkedIn माइक्रोसफ्ट बजेट SalesForce SAP Uber VMware वालमार्ट ल्याबहरू याहू
ब्याकट्र्याकिंग

समस्या पर्म्युटेसन लेटकोड समाधानले पूर्णाgers्कहरूको सरल अनुक्रम प्रदान गर्दछ र हामीलाई पूर्ण भेक्टर फिर्ता गर्न अनुरोध गर्दछ वा array दिईएको अनुक्रमको सबै क्रमश: को। त्यसो भए समस्या सुल्झाउनु भन्दा पहिले। हामी अनुमतिसँग परिचित हुनुपर्छ। त्यसो भए, क्रमांकन दिईएको पूर्णा .्कहरूको प्रबन्ध बाहेक अरू केही पनि हुँदैन। त्यसोभए, जब हामी भन्छौ कि हामीलाई अनुक्रमको सबै आदेशहरू आवश्यक छन्। हाम्रो मतलब यो छ कि हामीलाई दिइएको अनुक्रमको सबै सम्भावित प्रबन्धहरू प्रिन्ट गर्न वा फिर्ता गर्न आवश्यक छ। राम्रो बुझ्नको लागि केहि उदाहरणहरू हेरौं।

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

स्पष्टीकरण: अनुक्रममा १, २, write लेख्न सक्ने सबै तरिकाहरू आउटपुटको रूपमा दिइएका छन्। त्यहाँ क्रमशः १, २, write लेख्ने कुल ways तरिकाहरू छन्।

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

स्पष्टीकरण: ०, १ लेख्न केवल २ तरिकाहरू छन्।

प्युमटेसन लेटकोड समाधानको लागि ब्याट्र्याकिंग दृष्टिकोण

परम्युटेसन लेटकोड समाधान

समस्या पर्म्युटेसन लेटकोड समाधानले हामीलाई दिइएको अनुक्रमका सबै आवागमनहरू उत्पन्न गर्न सोध्यो। सामान्यतया, हामी एक क्रम उत्पन्न गर्न आवश्यक छ वा केहि अनुक्रम रिकर्जन जाने कुञ्जी हो। तर यहाँ पुनरावृत्ति वा ब्याट्र्याकिंग एक सानो मुश्किल छ। एक तरीकाले अनपिक गरिएको तत्वहरूबाट तत्व लिने र यसलाई उत्तरको अन्त्यमा राख्ने हुन सक्छ। यस तरिकाले क्रमशक्ति उत्पन्न गर्दछ र केहि निश्चित गर्न यो निश्चित गर्नुहोस् कि यो क्रमशक्ति उत्पन्न गरिएको छ र दोहोर्याउनु हुँदैन। तर यो गर्नुको सट्टा, हामी कार्य गर्नका लागि सरल तरिका खोज्ने प्रयास गर्छौं। के हुन्छ यदि हामी एलिमेन्ट छान्छौं र यसलाई हालको एलिमेन्टसँग बदल्छौं। फेरी अनुक्रमणिका पछिल्लो अनुक्रमणिकाका लागि सबै क्रमवाट उत्पन्न गर्न पुनरावर्ती कल गर्नुहोस्।

एक पटक हामी क्रमशः एक सूचक अगाडि उत्पन्न गर्नका साथ। हामी छनौट गरिएको तत्व हटाउँछौं, र त्यसपछि अर्को तत्व छान्छौं र प्रक्रिया दोहोर्याउँदछौं। यस तरिकाले हामी यो निश्चित गर्दछौं कि हामीले प्रत्येक अव्यवस्थित तत्व कम्तिमा एक पटक हालको स्थितिमा राख्यौं। र किनकि हामीले एउटा सानो सबप्रोब्लिममा रिकर्सिव कल गरेका छौं। सानो subproblem वर्तमान अनुक्रमणिका पछि सुरू हुने अनुक्रमको लागि क्रम उत्पन्न गर्दै। हालको क्रममा ती क्रमशब्दहरू थप्नाले वर्तमान सूचकांकमा सेट गरिएको एलिमेन्टको साथ क्रमबद्धको सेट पूरा गर्दछ। यस तरिकाले हामी एर्रेलाई बायाँ देखि दायाँ ट्रान्स गर्दै र समस्यालाई सानो सबप्रोब्लम्समा विभाजन गरिरहन्छौं। एक पटक हामी आवश्यकतामा पुगेपछि हामीले दा सम्भावित क्रमशक्ति उत्पन्न गरेका छौं र हामी यसलाई उत्तरमा थप्दछौं।

ब्याट्र्याकिंग कोड

सी ++ पर्म्युटेसन लेटकोड समाधानको लागि कोड

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

जटिलता विश्लेषण

समय जटिलता

O (Sigma (P (N, K)), जहाँ P को n वा आंशिक परिमितीको k आज्ञाकरण हो। अधिक औपचारिक रूपमा, P (N, k) = (N!) / ((Nk)!)।

ठाउँ जटिलता

O (N!), किनकी हामी सबै सम्भावित समाधानहरू भण्डारण गर्नुपर्दछ जुन N हो! आकारमा जहाँ N एर्रेको आकार छ।