Пермутације Леетцоде решење


Ниво тешкоће Средњи
Често питани у адобе амазонка јабука Атлассиан Блоомберг БитеДанце еБаи фацебоок гарена ГоДадди Голдман Сакс гоогле ЛинкедИн мицрософт пророчанство Салесфорце САП Убер ВМваре Валмарт Лабс иахоо
Бацктрацкинг

Проблем Пермутатионс Леетцоде Солутион пружа једноставан низ целих бројева и тражи од нас да вратимо комплетан вектор или поредак свих пермутација датог низа. Дакле, пре него што кренете у решавање проблема. Требали бисмо бити упознати са пермутацијама. Дакле, пермутација није ништа друго него распоред задатих целих бројева. Дакле, када кажемо да су нам потребне све пермутације низа. Мислимо да смо дужни да одштампамо или вратимо све могуће аранжмане датог низа. Погледајмо неколико примера за боље разумевање.

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.

Приступ враћања за пермутације Леетцоде решење

Пермутације Леетцоде решење

Проблем Пермутације Леетцоде Солутион тражили су од нас да генеришемо све пермутације датог низа. Генерално, од нас се захтева да генеришемо пермутацију или је нека рекурзија секвенце кључна. Али овде је рекурзија или враћање уназад помало незгодно. Један од начина је могао бити одабир елемента из неизабраних елемената и његово постављање на крај одговора. На овај начин генеришите пермутацију и некако се побрините да запамтите да је ова пермутација генерисана и да је не треба понављати. Али уместо да то учинимо, покушавамо да пронађемо једноставан начин за извршавање задатка. Шта ако одаберемо елемент и заменимо га са тренутним елементом. Затим упутите рекурзивни позив да бисте генерисали све пермутације за секвенцу један индекс након тренутног индекса.

Када завршимо са генерисањем пермутација један индекс унапред. Уклонимо одабрани елемент, а затим одаберемо други елемент и поновимо поступак. На овај начин осигуравамо да смо сваки неискоришћени елемент бар једном поставили у тренутни положај. И пошто смо рекурзивно позвали мањи подпроблем. Мањи потпроблем генерише пермутацију за секвенцу која почиње одмах након тренутног индекса. Додавањем тих пермутација у тренутну пермутацију завршава се сет пермутација елементом постављеним у тренутном индексу. На овај начин непрестано прелазимо низом слева надесно и делимо проблем на мање потпроблеме. Једном када достигнемо потребу генерисали смо могућу пермутацију и додали је одговору.

Код за враћање уназад

Ц ++ код за пермутације Леетцоде Солутион

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

Анализа сложености

Сложеност времена

О (Сигма (П (Н, К)), где је П к к пермутација од н или делимична пермутација. Формалније, П (Н, к) = (Н!) / ((Нк)!).

Сложеност простора

НА!), пошто морамо да чувамо сва могућа решења која су Н! у величини где је Н величина низа.