Bu leetcode problemində bir əvvəlcədən verdik array fərqli tam ədədlərdən mümkün olan bütün permutasiyaları çap edin.
Mündəricat
Nümunələr
Input
arr [] = {1, 2, 3}
Buraxılış
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Input
arr [] = {1, 2, 3, 4}
Buraxılış
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 problem perermutations üçün alqoritm
Bütün permutasiyalar backtracking istifadə edərək yaradıla bilər.
- Dizinin l-dən r-ə qədər bütün permütasiyalarını yaratmaq üçün l indeksindəki elementi düzəldin və l + 1-dən r-ə qədər təkrarlayın.
- L indeksində başqa bir elementi geri çəkin və düzəldin və l + 1-dən r-ə qədər təkrarlayın.
- Bütün permutasiyaları yaratmaq üçün yuxarıdakı addımları təkrarlayın.
Leetcode problemi perermutasiyalarının izahı
Nümunəni nəzərdən keçirək arr [] = {1, 2, 3}
Bir elementi birinci vəziyyətdə düzəldin, 1, ya da 2 və ya 3 seçimimiz var. İkinci səviyyə altındakı görüntü bu vəziyyəti təmsil edir. İkinci səviyyə birinci sütunda 1 birinci mövqedə, ikinci sütunda 2 birinci mövqedə və üçüncü sütunda 3 birinci mövqedə sabitlənir.
Bir elementi ilk mövqedə düzəltdikdən sonra, bir elementi ikinci mövqedə düzəldin, ikinci səviyyə və birinci sütunda vəziyyəti nəzərdən keçirin, yəni {1, 2, 3}, 1 birinci mövqedə sabitləndi, buna görə də 2 və ya 2 olan ikinci mövqe üçün 3 seçim var. İkinci vəziyyətin düzəldilməsi üçüncü vəziyyəti avtomatik olaraq düzəldir. Aydınlaşdırmaq üçün yuxarıdakı şəkilə baxın.
Bunu bütün hallar üçün edin və verilən massivin bütün mümkün permutasiyalarını yaradır.
JAVA Kodu
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 ++ kodu
#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 problem perermutations üçün mürəkkəblik analizi
Zaman Mürəkkəbliyi = O (n!)
burada n - massivdəki elementlərin sayı.
