Bagaimanakah saya boleh menjana semua pilih atur tatasusunan dengan cekap menggunakan pendekatan lelaran dalam Java?

Algoritma Permutasi

Untuk menjana semua pilih atur tatasusunan, pertimbangkan pendekatan berulang yang bermula dengan tatasusunan semasa dalam tertib menaik. Matlamatnya adalah untuk mengubahnya secara beransur-ansur menjadi tertib menurun dengan menukar elemen yang memecahkan corak menurun.

Algoritma Pseudokod

`
untuk (int tail = ind. panjang - 1 ekor > {

if (ind[tail - 1] < ind[tail]) { // still increasing

    // find last element that does not exceed ind[tail - 1]
    int s = ind.length - 1;
    while (ind[tail - 1] >= ind[s])
        s--;

    swap(ind, tail - 1, s);

    // reverse order of elements in the tail
    for (int i = tail, j = ind.length - 1; i < j; i++, j--)
        swap(ind, i, j);
    break;
}

}
`

Pelaksanaan

Berikut ialah contoh pelaksanaan dalam Java yang mengendalikan kedua-dua berbeza dan berulang elemen:

import java.util.Arrays;
import java.util.Iterator;
import java.lang.reflect.Array;

class Permutations<E> implements Iterator<E[]> {

    private E[] arr;
    private int[] ind;
    private boolean has_next;

    public E[] output; // next() returns this array

    Permutations(E[] arr) {
        this.arr = arr.clone();
        ind = new int[arr.length];

        // convert an array of any elements into an array of integers
        Map<E, Integer> hm = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            Integer n = hm.get(arr[i]);
            if (n == null) {
                hm.put(arr[i], i);
                n = i;
            }
            ind[i] = n.intValue();
        }
        Arrays.sort(ind); // start with ascending sequence of integers

        output = (E[]) Array.newInstance(arr.getClass().getComponentType(), arr.length);
        has_next = true;
    }

    public boolean hasNext() {
        return has_next;
    }

    public E[] next() {
        if (!has_next) {
            throw new NoSuchElementException();
        }

        for (int i = 0; i < ind.length; i++) {
            output[i] = arr[ind[i]];
        }

        // get next permutation
        has_next = false;
        for (int tail = ind.length - 1; tail > 0; tail--) {
            if (ind[tail - 1] < ind[tail]) { // still increasing

                // find last element that does not exceed ind[tail - 1]
                int s = ind.length - 1;
                while (ind[tail - 1] >= ind[s]) {
                    s--;
                }

                swap(ind, tail - 1, s);

                // reverse order of elements in the tail
                for (int i = tail, j = ind.length - 1; i < j; i++, j--) {
                    swap(ind, i, j);
                }

                has_next = true;
                break;
            }
        }

        return output;
    }

    private void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public void remove() {
        // not supported
    }
}

Contoh

Untuk tatasusunan [3, 4, 6, 2, 1], pilih atur adalah seperti berikut:

[3, 2, 1, 4, 6]
[3, 2, 1, 6, 4]
[3, 2, 4, 1, 6]
[3, 2, 4, 6, 1]
[3, 2, 6, 1, 4]
[3, 2, 6, 4, 1]
[3, 4, 1, 2, 6]
[3, 4, 1, 6, 2]
[3, 4, 2, 1, 6]
[3, 4, 2, 6, 1]
[3, 4, 6, 1, 2]
[3, 4, 6, 2, 1]
[3, 6, 1, 2, 4]
[3, 6, 1, 4, 2]
[3, 6, 2, 1, 4]
[3, 6, 2, 4, 1]
[3, 6, 4, 1, 2]
[3, 6, 4, 2, 1]
[4, 2, 1, 3, 6]
[4, 2, 1, 6, 3]
[4, 2, 3, 1, 6]
[4, 2, 3, 6, 1]
[4, 2, 6, 1, 3]
[4, 2, 6, 3, 1]
[4, 3, 1, 2, 6]
[4, 3, 1, 6, 2]
[4, 3, 2, 1, 6]
[4, 3, 2, 6, 1]
[4, 3, 6, 1, 2]
[4, 3, 6, 2, 1]
[4, 6, 1, 2, 3]
[4, 6, 1, 3, 2]
[4, 6, 2, 1, 3]
[4, 6, 2, 3, 1]
[4, 6, 3, 1, 2]
[4, 6, 3, 2, 1]
[6, 2, 1, 3, 4]
[6, 2, 1, 4, 3]
[6, 2, 3, 1, 4]
[6, 2, 3, 4, 1]
[6, 2, 4, 1, 3]
[6, 2, 4, 3, 1]
[6, 3, 1, 2, 4]
[6, 3, 1, 4, 2]
[6, 3, 2, 1, 4]
[6, 3, 2, 4, 1]
[6, 3, 4, 1, 2]
[6, 3, 4, 2, 1]
[6, 4, 1, 2, 3]
[6, 4, 1, 3, 2]
[6, 4, 2, 1, 3]
[6, 4, 2, 3, 1]
[6, 4, 3, 1, 2]
[6, 4, 3, 2, 1]

Atas ialah kandungan terperinci Bagaimanakah saya boleh menjana semua pilih atur tatasusunan dengan cekap menggunakan pendekatan lelaran dalam Java?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!