java - javaを使用してint配列の順列を生成する - エラー

Question

整数配列のすべての順列を生成する Java コードを作成しています。順列の数は正しくなっていますが、順列自体は正しくありません。

実行すると、次のようになります。

Input array Length
3
1
2
3
0Permutation is
1,  2,  3,  
##########################
1Permutation is
1,  3,  2,  
##########################
2Permutation is
3,  1,  2,  
##########################
3Permutation is
3,  2,  1,  
##########################
4Permutation is
1,  2,  3,  
##########################
5Permutation is
1,  3,  2,  
##########################
6  number of permutations obtained
BUILD SUCCESSFUL (total time: 3 seconds)


public class PermulteArray {

    public static int counter = 0;

    public static void Permute(int[] input, int startindex) {
        int size = input.length;

        if (size == startindex + 1) {
            System.out.println(counter + "Permutation is");
            for (int i = 0; i < size; i++) {
                System.out.print(input[i] + ",  ");
            }
            System.out.println();
            System.out.println("##########################");
            counter++;
        } else {
            for (int i = startindex; i < size; i++) {

                int temp = input[i];
                input[i] = input[startindex];
                input[startindex] = temp;
                Permute(input, startindex + 1);
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("Input array Length");
        int arraylength = in.nextInt();
        int[] input = new int[arraylength];
        for (int i = 0; i < arraylength; i++) {
            input[i] = in.nextInt();
        }
        counter = 0;
        Permute(input, 0);
        System.out.println(counter + "  number of permutations obtained");
    }
}

score 14 · Accepted Answer

int temp=input[i];
input[i]=input[startindex];
input[startindex]=temp;
Permute(input, startindex+1);

Permute を呼び出す前に要素を交換しましたが、for ループの反復全体で要素の一貫した位置を維持するために、後で再度交換する必要があります。

score 1 · Accepted Answer

これは、再帰呼び出しを使用して解決できます。

https://github.com/Pratiyush/Master/blob/master/Algorithm%20Tutorial/src/arrays/Permutations.java

public void swap(int[] arr, int i, int j)
{
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

public void permute(int[] arr, int i)
{
    if (i == arr.length)
    {
        System.out.println(Arrays.toString(arr));
        return;
    }
    for (int j = i; j < arr.length; j++)
    {
        swap(arr, i, j); 
        permute(arr, i + 1);  // recurse call
        swap(arr, i, j);      // backtracking
    }
} 

public static void main(String[] args) {

    Permutations permutations = new Permutations();
    int[] arr = {1, 2, 3,4};
    permutations.permute(arr, 0);
}

また、他のアプローチが利用可能です

score 1 · Accepted Answer

public class PermuteArray {

    public static void permute(char[] input2, int startindex) {

        if (input2.length == startindex) {
             displayArray(input2);
        } else {
            for (int i = startindex; i < input2.length; i++) {
                char[] input = input2.clone();
                char temp = input[i];
                input[i] = input[startindex];
                input[startindex] = temp;
                permute(input, startindex + 1);
            }
        }
    }


    private static void displayArray(char[] input) {
        for (int i = 0; i < input.length; i++) {
            System.out.print(input[i] + ";  ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        char[] input = { 'a', 'b', 'c', 'd'};
        permute(input, 0);
    }

}

score 1 · Accepted Answer

これをチェックしてください

for (int i = startindex; i < input2.length; i++) {
            char[] input = input2.clone();
            char temp = input[i];
            input[i] = input[startindex];
            input[startindex] = temp;
            permute(input, startindex + 1);
        }

java - javaを使用してint配列の順列を生成する - エラー

9 に答える 9

Related

Reference