Bagaimanakah Saya Boleh Menjana Semua Pilihatur Tatasusunan Menggunakan Algoritma Rekursif dan Bukan Rekursif?

Permutasi Tatasusunan: Penjelasan Mendalam

Untuk menjana pilih atur tatasusunan, adalah penting untuk memahami cara unsur-unsur disusun. Permutasi melibatkan penyusunan semula elemen tatasusunan untuk mencipta jujukan baharu. Bilangan pilih atur yang mungkin untuk tatasusunan dengan n elemen diberikan oleh n!.

Algoritma Rekursif

Salah satu cara untuk menjana pilih atur ialah menggunakan pendekatan rekursif, di mana anda bertukar-tukar elemen secara berulang dan gunakan pilih atur pada elemen tatasusunan yang tinggal.

public static void permute(java.util.List<Integer> arr, int k) {
    for (int i = k; i < arr.size(); i++) {
        java.util.Collections.swap(arr, i, k);
        permute(arr, k + 1);
        java.util.Collections.swap(arr, k, i);
    }
    if (k == arr.size() - 1) {
        System.out.println(java.util.Arrays.toString(arr.toArray()));
    }
}

Algoritma ini bermula dengan menukar elemen pertama dengan setiap elemen yang tinggal. Kemudian, ia secara rekursif menggunakan operasi yang sama pada elemen yang tinggal. Selepas setiap panggilan rekursif, elemen ditukar kembali ke kedudukan asalnya.

Algoritma Bukan Rekursif

Untuk pendekatan berulang, pertimbangkan langkah berikut:

1. Mulakan dengan tatasusunan yang diisih dalam tertib menaik.
2. Cari yang pertama indeks di mana jujukan gagal menurun (iaitu, di mana a[i] < a[i-1]).
3. Cari indeks terakhir yang nilainya lebih besar daripada atau sama dengan a[i-1 ].
4. Tukar a[i-1] dengan elemen pada indeks terakhir.
5. Terbalikkan susunan unsur dalam ekor tatasusunan (selepas indeks i-1).

Contoh: Mengatur Tatasusunan [3, 4, 6, 2, 1]

Algoritma Rekursif:

1. Tukar 3 dengan 4: [4, 3, 6, 2, 1]
2. Permud secara rekursif [4, 3, 6, 2, 1]
3. Tukar 3 dengan 6: [4, 6, 3, 2, 1]
4. Permud secara rekursif [4, 6, 3, 2, 1]
5. Teruskan sehingga semua pilih atur dijana

Algoritma Bukan Rekursif:

1. Mulakan dengan [1, 2, 3, 4, 6] (diisih menaik)
2. Jujukan sedang menurun, jadi teruskan ke Langkah 3
3. Cari indeks pertama di mana a[i] < a[i-1]: i = 4, sejak 3 < 4
4. Cari indeks terakhir di mana a[j] >= a[i-1]: j = 5, sejak 6 >= 3
5. Tukar a[i-1] dengan a[j]: [1, 2, 6, 3, 4, 5]
6. Terbalikkan ekor tatasusunan: [1, 2, 3, 4, 5, 6]
7. Ulang Langkah 3-6 sehingga tatasusunan berada dalam tertib menurun (menunjukkan semua pilih atur telah dijana)

Hasil untuk kedua-dua algoritma adalah sama: semua pilih atur yang mungkin dijana dan dicetak.

Atas ialah kandungan terperinci Bagaimanakah Saya Boleh Menjana Semua Pilihatur Tatasusunan Menggunakan Algoritma Rekursif dan Bukan Rekursif?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!