लेटकोड क्रमपरिवर्तन


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना सेब ByteDance ईबे Facebook गूगल माइक्रोसॉफ्ट ओरेकल
बैक ट्रैकिंग

इस लेटकोड समस्या के आधार पर हमने दिया है a सरणी अलग-अलग पूर्णांकों में, इसके सभी संभावित क्रमांकन प्रिंट करें।

उदाहरण

निवेश
गिरफ्तार [] = {१, १, १}
उत्पादन
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

निवेश
गिरफ्तार [] = {५, ५, १०, २०}
उत्पादन
1 2 3 4
1 2 4 3
2 1 3 4
2 1 4 3
1 3 2 4
1 3 4 2
2 3 1 4
2 3 4 1
1 4 3 2
1 4 2 3
2 4 3 1
2 4 1 3
3 2 1 4
3 2 4 1
4 2 3 1
4 2 1 3
3 1 2 4
3 1 4 2
4 3 2 1
4 3 1 2
3 4 1 2
3 4 2 1
4 1 3 2
4 1 2 3

Leetcode समस्या क्रमपरिवर्तन के लिए एल्गोरिथम

सभी क्रमपरिवर्तन का उपयोग बैकट्रैकिंग के द्वारा किया जा सकता है।

  1. इंडेक्स एल से आर तक एक सरणी के सभी क्रमपरिवर्तन उत्पन्न करने के लिए, इंडेक्स एल पर एक तत्व को ठीक करें और इंडेक्स एल + 1 से आर के लिए पुनरावृत्ति करें।
  2. अनुक्रमणिका l पर किसी अन्य तत्व को पीछे और ठीक करें और अनुक्रमणिका l + 1 से r के लिए पुनरावृत्ति करें।
  3. सभी क्रमचय उत्पन्न करने के लिए उपरोक्त चरणों को दोहराएं।

Leetcode समस्या के लिए स्पष्टीकरण क्रमपरिवर्तन

गिरफ्तार उदाहरण पर विचार करें [] = {1, 2, 3}

किसी तत्व को पहली स्थिति में ठीक करें, हमारे पास तीन विकल्प हैं 1, या 2, या 3. दूसरे स्तर के नीचे की छवि इस स्थिति का प्रतिनिधित्व करती है। दूसरे स्तर के पहले कॉलम में पहले स्थान पर तय किया गया है, दूसरे कॉलम में पहले स्थान पर 1 और तीसरे कॉलम में पहले स्थान पर तय किया गया है।

लेटकोड क्रमपरिवर्तन

पहली स्थिति में एक तत्व को ठीक करने के बाद, दूसरी स्थिति में एक तत्व को ठीक करें, दूसरे स्तर और पहले कॉलम में मामले पर विचार करें, अर्थात, {1, 2, 3}, 1 पहले स्थान पर तय किया गया है, इसलिए हम दूसरी स्थिति के लिए 2 विकल्प हैं जो या तो 2 या 3 है। दूसरी स्थिति को ठीक करके तीसरी स्थिति को स्वचालित रूप से ठीक करता है। स्पष्टीकरण के लिए ऊपर दी गई छवि देखें।

सभी मामलों के लिए यह करें और यह दिए गए सरणी के सभी संभावित क्रम उत्पन्न करेगा।

जावा कोड

public class LeetcodePermutations {
    // Function to generate all the permutations from l to r
    private static void permute(int[] arr, int l, int r) {
        if (l == r) {
            // Print this permutation
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }
        for (int i = l; i <= r; i++) {
            // Fix an element at index l
            swap(arr, l, i);
            // Recur for index l + 1 to r
            permute(arr, l + 1, r);
            // Back track
            swap(arr, l, i);
        }
    }

    // Function to swap element at index x and y of array arr
    private static void swap(int arr[], int x, int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
    
    public static void main(String[] args) {
        // Example
        int arr[] = new int[] {1, 2, 3};
        int n = arr.length;
        // Generate permutations from index 0 to n - 1
        permute(arr, 0, n - 1);
    }
}

C ++ कोड

#include<bits/stdc++.h> 
using namespace std;

// Function to swap element at index x and y of array arr
void swap(int *arr, int x, int y) {
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

// Function to generate all the permutations from l to r
void permute(int *arr, int l, int r, int n) {
    if (l == r) {
        // Print this permutation
        for (int i = 0; i < n; i++) {
            cout<<arr[i]<<" ";
        }
        cout<<endl;
        return;
    }
    for (int i = l; i <= r; i++) {
        // Fix an element at index l
        swap(arr, l, i);
        // Recur for index l + 1 to r
        permute(arr, l + 1, r, n);
        // Back track
        swap(arr, l, i);
    }
}

int main() {
    // Example
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    // Generate permutations from index 0 to n - 1
    permute(arr, 0, n - 1, n);
    return 0;
}
1 2 3                                                                                                                                         
1 3 2                                                                                                                                         
2 1 3                                                                                                                                         
2 3 1                                                                                                                                         
3 2 1                                                                                                                                         
3 1 2

Leetcode समस्या क्रमपरिवर्तन के लिए जटिलता विश्लेषण

समय जटिलता = पर!) 
जहाँ n सरणी में तत्वों की संख्या है।

संदर्भ