ප්‍රේරක ලීට්කෝඩ් විසඳුම


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් Apple ජංගම දුරකථන ඇට්ලසියන් බ්ලූම්බර්ග් ByteDance ඊ බේ ෆේස්බුක් Garena GoDaddy ගෝල්ඩ්මන් සැක්ස් ගූගල් LinkedIn මයික්රොසොෆ්ට් ඔරකල් Salesforce SAP Uber VMware වෝල්මාර්ට් ලැබ් යාහූ
පසුගාමී වීම

ගැටළුව ප්‍රේරක ලීට්කෝඩ් විසඳුම පූර්ණ සංඛ්‍යා අනුක්‍රමයක් සපයන අතර සම්පූර්ණ දෛශිකයක් ආපසු ලබා දෙන ලෙස අපෙන් ඉල්ලා සිටී. අරාව දී ඇති අනුක්‍රමයේ සියලු ප්‍රේරණයන්ගෙන්. එබැවින්, ගැටළුව විසඳීමට යාමට පෙර. අපි ප්‍රේරණයන් ගැන දැන සිටිය යුතුයි. එබැවින්, ප්‍රේරණයක් යනු දී ඇති පූර්ණ සංඛ්‍යා වල විධිවිධානයක් පමණි. ඉතින්, අපට අනුක්‍රමයක සියලු ප්‍රේර්‍යයන් අවශ්‍ය යැයි පැවසූ විට. අප අදහස් කරන්නේ දී ඇති අනුක්‍රමයේ ඇති සියලුම විධිවිධාන මුද්‍රණය කිරීම හෝ ආපසු ලබා දීම අවශ්‍ය බවයි. වඩා හොඳ අවබෝධය සඳහා උදාහරණ කිහිපයක් දෙස බලමු.

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 ප්‍රේරණයයි. වඩාත් විධිමත් ලෙස, P (N, k) = (N!) / ((Nk)!).

අභ්‍යවකාශ සංකීර්ණතාව

මත!), එන් විය හැකි සියලු විසඳුම් අප විසින් ගබඩා කළ යුතු බැවින්! ප්‍රමාණයෙන් N යනු අරාවේ ප්‍රමාණයයි.