Comment puis-je générer efficacement toutes les permutations d'un tableau en utilisant une approche itérative en Java ?

Algorithme de permutation

Pour générer toutes les permutations d'un tableau, envisagez une approche itérative qui commence par le tableau actuel par ordre croissant. Le but est de le transformer progressivement en ordre décroissant en échangeant les éléments qui brisent le schéma descendant.

Algorithme de pseudocode

`
for (int tail = ind. longueur - 1 ; queue > 0 ; {

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;
}

}
`

Implémentation

Voici un exemple d'implémentation en Java qui gère à la fois les tâches distinctes et répétées éléments :

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
    }
}

Exemple

Pour un tableau [3, 4, 6, 2, 1], les permutations sont les suivantes :

[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]

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!