Java中整数数组的排列算法 [英] Permutation algorithm for array of integers in Java

问题描述

我有一个工作示例来生成字符串中的所有字符排列，如下所示:

I have a working example to generate all char permutations in a String as below:

static ArrayList<String> permutations(String s) {
        if (s == null) {
            return null;
        }

        ArrayList<String> resultList = new ArrayList<String>();

        if (s.length() < 2) {
            resultList.add(s);

            return resultList;
        }

        int length = s.length();
        char currentChar;

        for (int i = 0; i < length; i++) {
            currentChar = s.charAt(i);

            String subString = s.substring(0, i) + s.substring(i + 1);

            ArrayList<String> subPermutations = permutations(subString);

            for (String item : subPermutations) {
                resultList.add(currentChar + item);
            }
        }

        return resultList;
    } 

我正在尝试实现相同的功能，但返回 ArrayList，并获取 int[] 作为参数.我正在递归地执行此操作，如下所示:

I am trying to implement the same function, but to return ArrayList, and to get int[] as the parameter. I am doing this recursively as below:

static ArrayList<int[]> permutations(int[] arr) {
        ArrayList<int[]> resultList = new ArrayList<int[]>();

        if (arr.length < 2) {
            resultList.add(arr);

            return resultList;
        } 

        for (int i = 0; i < arr.length; i++) {
            int currentItem = arr[i];
            int[] newArr = new int[arr.length - 1];
            int[] newPermutation = new int[arr.length];
            int j;

//          System.arraycopy(arr, 0, newArr, 0, i);
//          System.arraycopy(arr, i + 1, newArr, i, arr.length - i - 1);

            for (j = 0; j < i; j++) {
                newArr[j] = arr[j];
            }

            for (j = i + 1; j < arr.length; j++) {
                newArr[j - 1] = arr[j];
            }

            ArrayList<int[]> subPermutations = permutations(newArr);

            newPermutation[0] = currentItem;

//          for (int i1 = 0; i1 < subPermutations.size(); i1++) {
//              for (j = 0; j < subPermutations.get(i1).length; j++) {
//                  newPermutation[j + 1] = subPermutations.get(i1)[j];
//              }
//              
//              resultList.add(newPermutation);
//          }

            for (int[] item : subPermutations) {
                for (j = 0; j < item.length; j++) {
                    newPermutation[j + 1] = item[j];
                }

                resultList.add(newPermutation);
            }

//          return resultList;
        }

        return resultList;
    }

当传递大小为 0、1 和 2 的数组作为参数时，一切正常.对于大于 2 的所有其他内容，我得到正确的排列数，但它们会重复.这是 size == 3 的结果，并传递 { 1, 5, 4 }:

When passing arrays of size 0, 1, and 2 as the parameter, everything is fine. For everything else greater than 2, I get the correct number of permutations, but they repeat themselves. Here is the result for size == 3, and passing { 1, 5, 4 }:

1 4 5 
1 4 5 
5 4 1 
5 4 1 
4 5 1 
4 5 1

如果您之前遇到过这些问题，请给我一些建议.

Please give me some advice if you encountered these issues before.

提前致谢！

推荐答案

//这里是一个递归版本，并不太难提交给人类记忆！O(n!) 排列.

//Here is a recursive version that was not to hard to commit to human memory ! O(n!) permutations.

public static Set<Integer[]> getPermutationsRecursive(Integer[] num){
    if (num == null)
        return null;

    Set<Integer[]> perms = new HashSet<>();

    //base case
    if (num.length == 0){
        perms.add(new Integer[0]);
        return perms;
    }

    //shave off first int then get sub perms on remaining ints.
    //...then insert the first into each position of each sub perm..recurse

    int first = num[0];
    Integer[] remainder = Arrays.copyOfRange(num,1,num.length);
    Set<Integer[]> subPerms = getPermutationsRecursive(remainder);
    for (Integer[] subPerm: subPerms){
        for (int i=0; i <= subPerm.length; ++i){ // '<='   IMPORTANT !!!
            Integer[] newPerm = Arrays.copyOf(subPerm, subPerm.length+1);
            for (int j=newPerm.length-1; j>i; --j)
                newPerm[j] = newPerm[j-1];
            newPerm[i]=first;
            perms.add(newPerm);
        }
    }

    return perms;
}

这篇关于Java中整数数组的排列算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！