Bagaimana untuk Menjana Semua Pilihatur Tatasusunan, Termasuk Kes dengan Nilai Berulang?

Permutasi tatasusunan

Memandangkan tatasusunan integer berbeza, cari jumlah nombor dan senaraikan semua pilih atur yang mungkin bagi tatasusunan.

Kod

Kod berikut menyediakan algoritma rekursif untuk mencari pilih atur tatasusunan:

import java.util.*;

public class Permute {

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

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

    private static void swap(int[] a, int x, int y) {
        int temp = a[x];
        a[x] = a[y];
        a[y] = temp;
    }
}

Algoritma ini menjana semua pilih atur tatasusunan dengan menukar elemen pertama dengan setiap elemen lain dalam tatasusunan, dan kemudian secara rekursif memanggil algoritma pada tatasusunan yang tinggal .

Iterators dan Sambungan kepada kes nilai berulang

The kelemahan algoritma ini ialah ia tidak mengendalikan kes nilai berulang dalam tatasusunan. Untuk mengendalikan kes ini, kita boleh mengubah suai algoritma untuk menggunakan timbunan dan bukannya rekursi. Kod berikut menyediakan algoritma berulang untuk mencari pilih atur tatasusunan:

import java.util.*;

public class Permute {

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

    private static void permuteIterative(int[] a) {
        Stack<Integer> stack = new Stack<>();
        Set<Integer> visited = new HashSet<>();
        stack.push(0);
        visited.add(0);

        while (!stack.isEmpty()) {
            int k = stack.peek();
            if (k == a.length - 1) {
                System.out.println(Arrays.toString(a));
                stack.pop();
            } else {
                for (int i = k + 1; i < a.length; i++) {
                    if (!visited.contains(i)) {
                        swap(a, i, k);
                        stack.push(i);
                        visited.add(i);
                        break;
                    }
                }
                if (stack.peek() == k) {
                    stack.pop();
                    visited.remove(k);
                }
            }
        }
    }

    private static void swap(int[] a, int x, int y) {
        int temp = a[x];
        a[x] = a[y];
        a[y] = temp;
    }
}

Algoritma ini menggunakan tindanan untuk menjejak pilih atur semasa. Algoritma bermula dengan menolak elemen pertama tatasusunan ke tindanan. Kemudian, algoritma berulang kali memunculkan elemen daripada timbunan dan menukarnya dengan elemen seterusnya yang tidak dilawati dalam tatasusunan. Jika tiada lagi elemen yang tidak dilawati dalam tatasusunan, algoritma akan mengeluarkan elemen daripada tindanan dan meneruskan dengan elemen seterusnya dalam tindanan.

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