Permutasi Array di Java

1. Perkenalan

Pada artikel ini, kita akan melihat cara membuat permutasi array.

Pertama, kita akan mendefinisikan apa itu permutasi. Kedua, kita akan melihat beberapa kendala. Dan ketiga, kita akan melihat tiga cara untuk menghitungnya: secara rekursif, berulang, dan acak.

Kami akan fokus pada implementasi di Java dan karena itu tidak akan membahas banyak detail matematis.

2. Apa Itu Permutasi?

Permutasi himpunan adalah penataan ulang elemen-elemennya. Himpunan yang terdiri dari n elemen memiliki n! permutasi. Di sini n! adalah faktorial, yang merupakan hasil kali dari semua bilangan bulat positif yang lebih kecil atau sama dengan n .

2.1. Contoh

Array bilangan bulat [3,4,7] memiliki tiga elemen dan enam permutasi:

n! = 3! = 1 x 2 x 3 = 6

Permutasi: [3,4,7]; [3,7,4]; [4,7,3]; [4,3,7]; [7,3,4]; [7,4,3]

2.2. Kendala

Jumlah permutasi meningkat cepat dengan n . Meskipun hanya membutuhkan beberapa detik untuk menghasilkan semua permutasi sepuluh elemen, dibutuhkan dua minggu untuk menghasilkan semua permutasi dari 15 elemen:

3. Algoritma

3.1. Algoritma Rekursif

Algoritme pertama yang kami lihat adalah algoritme Heap. Ini adalah algoritma rekursif yang menghasilkan semua permutasi dengan menukar satu elemen per iterasi.

Array input akan dimodifikasi. Jika kita tidak menginginkannya, kita perlu membuat salinan dari array sebelum memanggil metode:

public static  void printAllRecursive( int n, T[] elements, char delimiter) { if(n == 1) { printArray(elements, delimiter); } else { for(int i = 0; i < n-1; i++) { printAllRecursive(n - 1, elements, delimiter); if(n % 2 == 0) { swap(elements, i, n-1); } else { swap(elements, 0, n-1); } } printAllRecursive(n - 1, elements, delimiter); } } 

Metode ini menggunakan dua metode pembantu:

private void swap(T[] input, int a, int b) { T tmp = input[a]; input[a] = input[b]; input[b] = tmp; }
private void printArray(T[] input) { System.out.print('\n'); for(int i = 0; i < input.length; i++) { System.out.print(input[i]); } } 

Di sini, kami menulis hasilnya ke System.out , namun, kami dapat dengan mudah menyimpan hasilnya dalam array atau dalam daftar.

3.2. Algoritma Iteratif

Algoritme Heap juga dapat diimplementasikan menggunakan iterasi:

int[] indexes = new int[n]; int[] indexes = new int[n]; for (int i = 0; i < n; i++) { indexes[i] = 0; } printArray(elements, delimiter); int i = 0; while (i < n) { if (indexes[i] < i) { swap(elements, i % 2 == 0 ? 0: indexes[i], i); printArray(elements, delimiter); indexes[i]++; i = 0; } else { indexes[i] = 0; i++; } } 

3.3. Permutasi dalam Urutan Leksikografis

Jika elemennya sebanding, kita dapat menghasilkan permutasi yang diurutkan berdasarkan urutan alami elemen:

public static 
    
      void printAllOrdered( T[] elements, char delimiter) { Arrays.sort(elements); boolean hasNext = true; while(hasNext) { printArray(elements, delimiter); int k = 0, l = 0; hasNext = false; for (int i = elements.length - 1; i > 0; i--) { if (elements[i].compareTo(elements[i - 1]) > 0) { k = i - 1; hasNext = true; break; } } for (int i = elements.length - 1; i > k; i--) { if (elements[i].compareTo(elements[k]) > 0) { l = i; break; } } swap(elements, k, l); Collections.reverse(Arrays.asList(elements).subList(k + 1, elements.length)); } } 
    

Algoritme ini memiliki operasi kebalikan di setiap iterasi dan oleh karena itu kurang efisien pada larik daripada algoritme Heap.

3.4. Algoritma Acak

Jika n besar, kita dapat membuat permutasi acak dengan mengacak array:

Collections.shuffle(Arrays.asList(elements));

Kami dapat melakukan ini beberapa kali untuk menghasilkan sampel permutasi.

Kita mungkin membuat permutasi yang sama lebih dari sekali, namun, untuk nilai n yang besar , peluang untuk menghasilkan permutasi yang sama dua kali adalah rendah.

4. Kesimpulan

Ada banyak cara untuk menghasilkan semua permutasi array. Dalam artikel ini, kita melihat algoritma Heap rekursif dan iteratif dan cara menghasilkan daftar permutasi yang diurutkan.

Tidak mungkin membuat semua permutasi untuk array besar, oleh karena itu, sebagai gantinya, kita dapat membuat permutasi acak.

Penerapan semua cuplikan kode dalam artikel ini dapat ditemukan di repositori Github kami.