java - 如何使用递归方法在 ArrayList 上保留不同的值？

Question

我正在使用递归方法进行排列，并且我想将排列保留在 ArrayList 中。我正在这样做，因为如果一个排列等于另一个排列，我想删除它——比如 123 等于 132，124 等于 142。我想避免重复。

排列是这样的：

(1) : 1 2 3 
(2) : 1 2 4 
(3) : 1 3 2 
(4) : 1 3 4
(5) : 1 4 2 
(6) : 1 4 3 
(7) : 2 1 3 
(8) : 2 1 4 
(9) : 2 3 1 
(10) : 2 3 4 
(11) : 2 4 1 
(12) : 2 4 3 
(13) : 3 1 2 
(14) : 3 1 4
(15) : 3 2 1
(16) : 3 2 4
(17) : 3 4 1 
(18) : 3 4 2
(19) : 4 1 2
(20) : 4 1 3 
(21) : 4 2 1
(22) : 4 2 3 
(23) : 4 3 1 
(24) : 4 3 2

但是当我要求打印 ArrayList 时，列表是这样的：

432
432
432
432
432
432
432
432
432
432
432
432
432
432
432
432
432
432
432
432
432
432
432
432

这是代码：（方法'getCyclesThroughPermutation'在main中被调用）

private static int cont = 0;
private static int[] permutation;

public static void getCyclesThroughPermutation(byte[][] matrix, int vertices){
    
    allPermutations = new ArrayList<>();
    
    /* This will represent all the vertices. */
    int allVertices[] = new int[vertices];

    /* Assigning values for the vertices array.*/
    int value = 0;
    for (int i = 0; i < vertices; i++){
        value++;
        allVertices[i] = value;
    } 

    /* Calls the permute method. */
    App.permute(allVertices);
}

public static ArrayList<int[]> allPermutations = new ArrayList<>();


/**
 * Main method: receives the array whose elements will be permutated.
 * @param vertices
*/
public static void permute(int[] vertices) {

    //i < vertices.length
    for (int i = 3; i < 4; i++){
        permutation = new int[i];
        permute(vertices, 0, allPermutations);
    }

    for (int i = 0; i < allPermutations.size(); i++){
        System.out.println();
        for (int j = 0; j < allPermutations.get(i).length; j++){
            System.out.print(allPermutations.get(i)[j]);
        }
    }

}

/**
 * Recursive method that implements the permutations.
 * @param vertices
 * @param n
*/
private static void permute(int[] vertices, int n, ArrayList<int[]> allPermutations) {



    /* If the given number is equal to the permutation array length: */
    if (n == permutation.length) {
        /* Count plus 1 (permutation accomplished). */
        cont++;

        // for (int i=0; i < permutation.length; i++) System.out.print(permutation[i] + " ");
        
        int[] clone = permutation.clone();
        Arrays.sort(clone);

        if(!allPermutations.contains(clone)){
            //System.out.println("Não sou um clone.");
            allPermutations.add(permutation);
            printPermutation();
        }
        else {
            //System.out.println("Sou um clone.");
        }

    } else {
        /* For each vertice of the vertices array: */
        for (int i=0; i < vertices.length; i++) {

            /* Boolean that keeps track if will be repetitions. */
            boolean found = false;

            /* For each index of the permutation array: */
            for (int j = 0; j < n; j++) {
                /* If the values are equal, the found variable will be true. */
                if (permutation[j]==vertices[i]) found = true;
            }

            /* If there's no equal values: */
            if (!found) {
                /* The permutation array in the n index will be equal to the vertice. */
                permutation[n] = vertices[i];
                /* And now, we permute again, but the next index will change. */
                permute(vertices, n+1, allPermutations);
            }
        }
    }
}

private static void printPermutation() {
    System.out.println();
    System.out.print("(" + cont + ") : ");
    for (int i=0; i < permutation.length; i++) System.out.print(permutation[i] + " ");
}

标签： javarecursionarraylist