Bagaimana untuk Menjana Semua Pilihatur Unik Tatasusunan, Termasuk Mengendalikan Elemen Berulang?

Permutasi tatasusunan

Pilihan tatasusunan ialah semua cara yang mungkin untuk menyusun unsur tatasusunan dalam susunan yang berbeza. Sebagai contoh, tatasusunan [1, 2, 3] mempunyai pilih atur berikut:

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

Terdapat beberapa algoritma untuk menjana pilih atur tatasusunan. Salah satu algoritma yang paling biasa ialah algoritma rekursif yang menjana semua pilih atur tatasusunan yang lebih kecil dengan menambahkan elemen baharu pada penghujung setiap pilih atur tatasusunan yang lebih kecil.

Berikut ialah pelaksanaan algoritma rekursif dalam Java :

import java.util.List;

public class Permute {

    public static void main(String[] args) {
        int[] a = new int[]{3, 4, 6, 2, 1};
        permute(a, 0);
    }

    static void permute(int[] a, int k) {
        for (int i = k; i < a.length; i++) {
            java.util.Collections.swap(a, i, k);
            permute(a, k + 1);
            java.util.Collections.swap(a, i, k);
        }
        if (k == a.length - 1) {
            System.out.println(java.util.Arrays.toString(a));
        }
    }
}

Kod di atas mencetak semua pilih atur tatasusunan a ke konsol.

Mengendalikan elemen berulang

Algoritma rekursif di atas tidak mengendalikan elemen berulang dengan betul. Contohnya, jika tatasusunan a mengandungi elemen berulang, maka algoritma akan menjana pilih atur pendua.

Untuk mengendalikan elemen berulang, kita boleh menggunakan algoritma berbeza yang dipanggil algoritma Heap. Algoritma Heap menjana semua pilih atur tatasusunan dengan menukar dua elemen tatasusunan secara berulang.

Berikut ialah pelaksanaan algoritma Heap dalam Java:

import java.util.List;

public class Permute {

    public static void main(String[] args) {
        int[] a = new int[]{3, 3, 4, 4, 6, 2, 1};
        permute(a, 0);
    }

    static void permute(int[] a, int k) {
        if (k == a.length - 1) {
            System.out.println(java.util.Arrays.toString(a));
        } else {
            for (int i = k; i < a.length; i++) {
                if (i == k || a[i] != a[k]) {
                    java.util.Collections.swap(a, i, k);
                    permute(a, k + 1);
                    java.util.Collections.swap(a, i, k);
                }
            }
        }
    }
}

Kod di atas mencetak semua pilih atur unik daripada tatasusunan a ke konsol.

Atas ialah kandungan terperinci Bagaimana untuk Menjana Semua Pilihatur Unik Tatasusunan, Termasuk Mengendalikan Elemen Berulang?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!