פּערמיוטיישאַנז לעעטקאָדע סאַלושאַן


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַדאָובי אַמאַזאָן עפּל אַטלאַססיאַן בלומבערג ביטעדאַנסע עבייַ facebook גאַרענאַ גאָדאַדדי גאָלדמאַן סאַקס גוגל לינקעדין מייקראָסאָפֿט אָראַקל סאַלעספאָרסע זאַפט ובער וומוואַרע וואַלמאַרט לאַבס יאַהאָאָ
Backtracking

דער פּראָבלעם פּערמוטאַטיאָנס לעעטקאָדע סאַלושאַן גיט אַ פּשוט סיקוואַנס פון ינטאַדזשערז און פרעגט אונדז צו צוריקקומען אַ גאַנץ וועקטאָר אָדער מענגע פון אַלע פּערמיוטיישאַנז פון די געגעבן סיקוואַנס. אַזוי איידער איר גיין צו סאַלווינג די פּראָבלעם. מיר זאָל זיין באַקאַנט מיט פּערמיוטיישאַנז. אַזוי, אַ פּערמיוטיישאַן איז גאָרנישט אָבער אַ אָרדענונג פון געגעבן ינטאַדזשערז. אַזוי, ווען מיר זאָגן אַז מיר דאַרפֿן אַלע פּערמיוטיישאַנז פון אַ סיקוואַנס. מיר מיינען אַז מיר מוזן דרוקן אָדער צוריקקומען אַלע מעגלעך עריינדזשמאַנץ פון די געגעבן סיקוואַנס. זאל ס קוק אין עטלעכע ביישפילן פֿאַר בעסער פארשטאנד.

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.

באַקקטראַקקינג צוגאַנג פֿאַר פּערמיוטיישאַנז לעעטקאָדע סאַלושאַן

פּערמיוטיישאַנז לעעטקאָדע סאַלושאַן

דער פּראָבלעם פּערמוטאַטיאָנס לעעטקאָדע סאַלושאַן געבעטן אונדז צו דזשענערייט אַלע פּערמיוטיישאַנז פון די געגעבן סיקוואַנס. אין אַלגעמיין, מיר דאַרפֿן צו דזשענערייט אַ פּערמיוטיישאַן אָדער עטלעכע סיקוואַנס רעקורסיאָן איז דער שליסל צו גיין. אָבער דאָ, די רעקורסיאָן אָדער באַקקטראַקקינג איז אַ ביסל טריקי. איין וועג קען האָבן געווען פּיקינג אַן עלעמענט פֿון ניט-פּיקט עלעמענטן און שטעלן עס אין די סוף פון די ענטפער. דער וועג דזשענערייט אַ פּערמיוטיישאַן און עפעס מאַכן זיכער צו געדענקען אַז די פּערמיוטיישאַן איז דזשענערייטאַד און זאָל ניט זיין ריפּיטיד. אָבער אַנשטאָט פון דעם, מיר פּרובירן צו געפֿינען אַ פּשוט וועג צו דורכפירן די אַרבעט. וואָס אויב מיר קלייַבן אַן עלעמענט און ויסבייַטן עס מיט דעם קראַנט עלעמענט. דערנאָך רוף אַ רעקורסיווע רוף צו דזשענערייט אַלע פּערמיוטיישאַנז פֿאַר די סיקוואַנס איין אינדעקס נאָך דעם קראַנט אינדעקס.

אַמאָל מיר האָבן געענדיקט די דזשענערייטינג פּערמיוטיישאַנז איין אינדעקס פאָרויס. מיר באַזייַטיקן די פּיקט עלעמענט און קלייַבן אַן אנדערן עלעמענט און איבערחזרן די פּראָצעדור. אויף דעם וועג מיר מאַכן זיכער אַז מיר האָבן שטעלן יעדער אַניוזד עלעמענט לפּחות אַמאָל אין די קראַנט שטעלע. און זינט מיר געמאכט אַ רעקורסיווע רוף צו אַ קלענערער סאַב-פּראָבלעם. דער קלענערער סאַב-פּראָבלעם איז דזשענערייטינג די פּערמיוטיישאַן פֿאַר די סיקוואַנס סטאַרטינג פּונקט נאָך די קראַנט אינדעקס. אַדדינג די פּערמיוטיישאַנז צו די קראַנט פּערמיוטיישאַן קאַמפּליץ אַ סכום פון פּערמיוטיישאַן מיט אַן עלעמענט שטעלן אין דעם קראַנט אינדעקס. אויף דעם וועג, מיר פאָרזעצן צו פאָרן די מענגע פֿון לינקס צו רעכט און דיוויד די פּראָבלעם אין קלענערער סאַב-פּראָבלעמס. אַמאָל מיר דערגרייכן דעם נויט, מיר האָבן דזשענערייטאַד אַ מעגלעך פּערמיוטיישאַן און מיר לייגן עס צו דעם ענטפער.

באַקקטראַקקינג קאָד

C ++ קאָד פֿאַר פּערמיוטיישאַנז לעעטקאָדע סאַלושאַן

#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

Java קאוד פֿאַר פּערמיוטיישאַנז Leetcode סאַלושאַן

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 אָדער פּאַרטיייש פּערמיוטיישאַן. מער פאָרמאַללי, P (N, k) = (N!) / ((Nk)!).

ספעיס קאַמפּלעקסיטי

אָ (ען!), זינט מיר האָבן צו קראָם אַלע די מעגלעך סאַלושאַנז וואָס זענען N! אין גרייס ווו N איז די גרייס פון דעם מענגע.