使用Java生成整数数组的排列--错误

Question

使用Java生成整数数组的排列--错误

8

我正在编写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");
    }
}

- Manas Paldhe

请写下您期望的输出和实际输出。 - Bhavik Ambani

1

你需要什么帮助？首先，我会修复你的代码和输出格式，使其更易于阅读。然后，我会在调试器中逐步执行代码，以查看它正在做什么。 - Peter Lawrey

对于大小为3，输入数组[1,2,3]，我应该得到[1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]、[3,2,1]中的任意一种顺序... 但我得到的是... 1，2，3， 1，3，2， 3，1，2， 3，2，1， 1，2，3， 1，3，2。 - Manas Paldhe

-1 这个问题显示出零努力（复制粘贴代码和输出不被视为“努力”）。请阅读 SSCCE。 - Bohemian

我也使用了调试器...基本上我认为发生的情况是当调用Permute（int [] input，int startindex）时（应排列子阵列startindex ... end），在几次递归调用后修改了输入数组，这对我来说是意外的。 - Manas Paldhe

解释得更清楚一些... 首次调用是 Permute([1,2,3], 0) -- 调用 Permute([1,2,3],1) -- 调用 Permute([1,2,3],2) 并打印... -- 调用 Permute([1,3,2],2) 并打印... -- 调用 Permute([3,2,1],2) 我期望它在这里调用 Permute([2,1,3),2)... 哪里错了... - Manas Paldhe

9个回答

11

这是我迄今为止看过的最好的解决方案:

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

- Sandip Subedi

1

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

}

- poonam

你能否请澄清一下你所做的更改？ - Simon MᶜKenzie

我添加了以下代码：

temp = input[i];
input[i] = input[startindex];
input[startindex] = temp;

在下面：Permute(input, startindex + 1);进行排列。 - poonam

1

你可以使用递归调用来解决这个问题。

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

此外，还有其他方法可用于

- Pratiyush Kumar Singh

1

检查一下这个。

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

- Mihai Petrovici

1

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

}

- Mihai Petrovici

0

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

/**
 * 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

- Michail Alexakis

虽然这个链接可能回答了问题，但最好在此处包含答案的基本部分并提供参考链接。如果链接页面更改，仅有链接的答案可能会失效。 - slfan

1

我根据 @slfan 的评论重写了答案。 - Michail Alexakis

0

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

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

- Abhinav Katyayen

0

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

- Alexey Godin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- fgb · Accepted Answer

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

你在调用Permute之前交换了一个元素，但你需要在后面再次交换回去，以保持for循环迭代过程中元素位置的一致性。