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 11 · Accepted Answer

这是迄今为止我见过的最好的解决方案：

public static void main(String[] args) {
    int[] a = { 1, 2, 3, 4, 5, 6 };
    permute(0, a);
}

public static void permute(int start, int[] input) {
    if (start == input.length) {
        //System.out.println(input);
        for (int x : input) {
            System.out.print(x);
        }
        System.out.println("");
        return;
    }
    for (int i = start; i < input.length; i++) {
        // swapping
        int temp = input[i];
        input[i] = input[start];
        input[start] = temp;
        // swap(input[i], input[start]);

        permute(start + 1, input);
        // swap(input[i],input[start]);

        int temp2 = input[i];
        input[i] = input[start];
        input[start] = temp2;
    }
}

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

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

//This will give correct output 

import java.util.Scanner;

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);
                temp = input[i];
                input[i] = input[startindex];
                input[startindex] = temp;
            }
        }
    }

    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 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 0 · Accepted Answer

我多次使用的解决方案（主要用于测试目的）如下。它基于众所周知的算法以按字典顺序生成排列（无递归）：

/**
 * Compute next (in lexicographic order) permutation and advance to it.
 *
 * Find greater index i for which a j exists, such that:
 * j > i and a[i] < a[j] (i.e. the 1st non-inversion).
 * For those j satisfying the above, we pick the greatest.
 * The next permutation is provided by swapping
 * items at i,j and reversing the range a[i+1..n]
 */
void advanceToNext() {
    // The array `current` is the permutation we start from
    // Find i when 1st non-inversion happens
    int i = n - 2;
    while (i >= 0 && current[i] >= current[i + 1])
        --i;

    if (i < 0) {
        // No next permutation exists (current is fully reversed)
        current = null;
        return;
    }

    // Find greater j for given i for 1st non-inversion
    int j = n - 1;
    while (current[j] <= current[i])
        --j;

    // Note: The range a[i+1..n] (after swap) is reverse sorted
    swap(current, i, j); // swap current[i] <-> current[j]
    reverse(current, i + 1, n); // reverse range [i+1..n]
}

一个完整的解决方案（以类的形式）在这里： https ://gist.github.com/drmalex07/345339117fef6ca47ca97add4175011f

score 0 · Accepted Answer

我对这个问题有简单的答案，你可以试试这个。

public class PermutationOfString {
    public static void main(String[] args) {
        permutation("123");
    }

    private static void permutation(String string) {
        printPermutation(string, "");
    }

    private static void printPermutation(String string, String permutation) {
        if (string.length() == 0) {
            System.out.println(permutation);
            return;
        }

        for (int i = 0; i < string.length(); i++) {
            char toAppendToPermutation = string.charAt(i);
            String remaining = string.substring(0, i) + string.substring(i + 1);

            printPermutation(remaining, permutation + toAppendToPermutation);
        }
    }
}

score 0 · Accepted Answer

import java.util.ArrayList;

public class RecursivePermGen {

    void permGen(int n, int m, ArrayList<Integer> cur) {
        if(m == 0) {
            System.out.println(cur);
            return;
        }
        for(int i = 1; i <= n; i++) {
            cur.add(0, i);
            permGen(n, m-1, cur);
            cur.remove(0);
        }

    }

    public static void main(String[] args) {
        RecursivePermGen pg = new RecursivePermGen();
        ArrayList<Integer> cur = new ArrayList<Integer>();

        pg.permGen(2, 2, cur);
    }
}

java - 使用 java 生成 int 数组的排列 -- 错误

9 回答 9

Related

Reference