வரிசைமாற்றங்கள் லீட்கோட் தீர்வு


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் ஆப்பிள் அட்லாசியன் ப்ளூம்பெர்க் ByteDance ஈபே பேஸ்புக் Garena GoDaddy கோல்ட்மேன் சாக்ஸ் கூகிள் லின்க்டு இன் மைக்ரோசாப்ட் ஆரக்கிள் விற்பனைக்குழு எஸ்ஏபி கிழித்து , 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 வரிசைமாற்றமாகும். இன்னும் முறையாக, பி (என், கே) = (என்!) / ((என்.கே)!).

விண்வெளி சிக்கலானது

ஓ (என்!), N ஆக இருக்கும் அனைத்து தீர்வுகளையும் நாம் சேமிக்க வேண்டும் என்பதால்! N என்பது வரிசையின் அளவு.