ಕ್ರಮಪಲ್ಲಟನೆಗಳು ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ  


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಡೋಬ್ ಅಮೆಜಾನ್ ಆಪಲ್ Atlassian ಬ್ಲೂಮ್ಬರ್ಗ್ ಬೈಟ್ ಡೇನ್ಸ್ ಇಬೇ ಫೇಸ್ಬುಕ್ Garena GoDaddy ಗೋಲ್ಡ್ಮನ್ ಸ್ಯಾಚ್ಸ್ ಗೂಗಲ್ ಸಂದೇಶ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಒರಾಕಲ್ ಸೇಲ್ಸ್ಫೋರ್ಸ್ ಸ್ಯಾಪ್ ಉಬರ್ ವರೆ ವಾಲ್ಮಾರ್ಟ್ ಲ್ಯಾಬ್ಸ್ ಯಾಹೂ
ಅಲ್ಗಾರಿದಮ್ಗಳು ಬ್ಯಾಕ್‌ಟ್ರಾಕಿಂಗ್ ಕೋಡಿಂಗ್ ಸಂದರ್ಶನ ಸಂದರ್ಶನ ಪೂರ್ವಭಾವಿ ಲೀಟ್‌ಕೋಡ್ LeetCodeSolutions

ಸಮಸ್ಯೆ ಕ್ರಮಪಲ್ಲಟನೆಗಳ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವು ಪೂರ್ಣಾಂಕಗಳ ಸರಳ ಅನುಕ್ರಮವನ್ನು ಒದಗಿಸುತ್ತದೆ ಮತ್ತು ಸಂಪೂರ್ಣ ವೆಕ್ಟರ್ ಅನ್ನು ಹಿಂತಿರುಗಿಸಲು ಕೇಳುತ್ತದೆ ಅಥವಾ ಸರಣಿ ಕೊಟ್ಟಿರುವ ಅನುಕ್ರಮದ ಎಲ್ಲಾ ಕ್ರಮಪಲ್ಲಟನೆಗಳಲ್ಲಿ. ಆದ್ದರಿಂದ, ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವ ಮೊದಲು. ನಾವು ಕ್ರಮಪಲ್ಲಟನೆಗಳೊಂದಿಗೆ ಪರಿಚಿತರಾಗಿರಬೇಕು. ಆದ್ದರಿಂದ, ಕ್ರಮಪಲ್ಲಟನೆಯು ನಿರ್ದಿಷ್ಟ ಪೂರ್ಣಾಂಕಗಳ ಜೋಡಣೆಯಲ್ಲದೆ ಮತ್ತೇನಲ್ಲ. ಆದ್ದರಿಂದ, ನಮಗೆ ಒಂದು ಅನುಕ್ರಮದ ಎಲ್ಲಾ ಕ್ರಮಪಲ್ಲಟನೆಗಳು ಬೇಕು ಎಂದು ಹೇಳಿದಾಗ. ನಿರ್ದಿಷ್ಟ ಅನುಕ್ರಮದ ಎಲ್ಲಾ ವ್ಯವಸ್ಥೆಗಳನ್ನು ನಾವು ಮುದ್ರಿಸಬೇಕು ಅಥವಾ ಹಿಂದಿರುಗಿಸಬೇಕು ಎಂದು ನಾವು ಅರ್ಥೈಸುತ್ತೇವೆ. ಉತ್ತಮ ತಿಳುವಳಿಕೆಗಾಗಿ ಕೆಲವು ಉದಾಹರಣೆಗಳನ್ನು ನೋಡೋಣ.

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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ  

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಸಿಗ್ಮಾ (ಪಿ (ಎನ್, ಕೆ)), ಇಲ್ಲಿ P ಎಂಬುದು n ಅಥವಾ ಭಾಗಶಃ ಕ್ರಮಪಲ್ಲಟನೆಯ k ಕ್ರಮಪಲ್ಲಟನೆಯಾಗಿದೆ. ಹೆಚ್ಚು ly ಪಚಾರಿಕವಾಗಿ, ಪಿ (ಎನ್, ಕೆ) = (ಎನ್!) / ((ಎನ್ಕೆ)!).

ಸಹ ನೋಡಿ
ಉಪ-ಸರಣಿಗಳ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ಹಿಮ್ಮುಖಗೊಳಿಸುವ ಮೂಲಕ ಎರಡು ಅರೇಗಳನ್ನು ಸಮಾನಗೊಳಿಸಿ

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್!), ಏಕೆಂದರೆ ನಾವು ಎನ್ ಆಗಿರುವ ಎಲ್ಲ ಪರಿಹಾರಗಳನ್ನು ಸಂಗ್ರಹಿಸಬೇಕಾಗುತ್ತದೆ! ಗಾತ್ರದಲ್ಲಿ N ಎಂಬುದು ರಚನೆಯ ಗಾತ್ರವಾಗಿದೆ.