Wie generiert man alle Permutationen eines Arrays, einschließlich Fälle mit wiederholten Werten?

Permutation des Arrays

Ermitteln Sie anhand eines Arrays unterschiedlicher Ganzzahlen die Gesamtzahl und listen Sie alle möglichen Permutationen des Arrays auf.

Code

Der folgende Code stellt einen rekursiven Algorithmus zum Finden des bereit Permutationen eines Arrays:

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

Dieser Algorithmus generiert alle Permutationen des Arrays, indem er das erste Element mit jedem der anderen Elemente im Array austauscht und dann den Algorithmus rekursiv für das verbleibende Array aufruft.

Iteratoren und Erweiterung auf den Fall wiederholter Werte

Der Nachteil dieses Algorithmus besteht darin, dass er behandelt nicht den Fall wiederholter Werte im Array. Um diesen Fall zu behandeln, können wir den Algorithmus so ändern, dass er einen Stapel anstelle einer Rekursion verwendet. Der folgende Code stellt einen iterativen Algorithmus zum Ermitteln der Permutationen eines Arrays bereit:

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

Dieser Algorithmus verwendet einen Stapel, um die aktuelle Permutation zu verfolgen. Der Algorithmus beginnt damit, das erste Element des Arrays auf den Stapel zu verschieben. Anschließend entfernt der Algorithmus wiederholt Elemente aus dem Stapel und tauscht sie mit dem nächsten nicht besuchten Element im Array aus. Wenn das Array keine weiteren nicht besuchten Elemente enthält, entfernt der Algorithmus das Element vom Stapel und fährt mit dem nächsten Element im Stapel fort.

Das obige ist der detaillierte Inhalt vonWie generiert man alle Permutationen eines Arrays, einschließlich Fälle mit wiederholten Werten?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!