在Java中的整数数组置换算法 [英] Permutation algorithm for array of integers in Java

问题描述

我有一个工作示例来生成一个String作为下面的所有字符排列：

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，我得到排列的正确数目，但他们重复自己。这里为大小== 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.

在此先感谢！

推荐答案

下面是包含使用泛型的解决方案的类。该API是一个有点不同，那么你指定什么，但要灵活得多。最容易看到的例子。的请注意，输入可能有更多的约束比我检查什么在这里！的

Below is a class containing a solution using generics. The API is a bit different then what you specified but far more flexible. Easiest to see with examples. Note that the inputs probably have more constraints than what I'm checking here!

public static final class Permutations {
    private Permutations() {}

    public static <T> List<T[]> get(Class<T> itemClass, T... itemsPool) {
        return get(itemsPool.length, itemClass, itemsPool);
    }

    public static <T> List<T[]> get(int size, Class<T> itemClass, T... itemsPool) {
        if (size < 1) {
            return new ArrayList<T[]>();
        }

        int itemsPoolCount = itemsPool.length;

        List<T[]> permutations = new ArrayList<T[]>();
        for (int i = 0; i < Math.pow(itemsPoolCount, size); i++) {
            T[] permutation = (T[]) Array.newInstance(itemClass, size);
            for (int j = 0; j < size; j++) {
                // Pick the appropriate item from the item pool given j and i
                int itemPoolIndex = (int) Math.floor((double) (i % (int) Math.pow(itemsPoolCount, j + 1)) / (int) Math.pow(itemsPoolCount, j));
                permutation[j] = itemsPool[itemPoolIndex];
            }
            permutations.add(permutation);
        }

        return permutations;
    }
}

示例用法

调用 Permutations.get（2 Integer.class，1，0，-1）; 将返回整数数组以下列表：

Calling Permutations.get(2, Integer.class, 1, 0, -1); will return the following list of integer arrays:

[ 1,  1]
[ 0,  1]
[-1,  1]
[ 1,  0]
[ 0,  0]
[-1,  0]
[ 1, -1]
[ 0, -1]
[-1, -1]

调用 Permutations.get（3 Integer.class，1，0，-1）; 将返回整数数组列表如下。的注意，这个例子是，除了现在是3的第一个参数相同的第一个的：

Calling Permutations.get(3, Integer.class, 1, 0, -1); will return the following list of integer arrays. Note that this example is identical to the first except for the first argument which is now 3:

[ 1,  1,  1]
[ 0,  1,  1]
[-1,  1,  1]
[ 1,  0,  1]
[ 0,  0,  1]
[-1,  0,  1]
[ 1, -1,  1]
[ 0, -1,  1]
[-1, -1,  1]
[ 1,  1,  0]
[ 0,  1,  0]
[-1,  1,  0]
[ 1,  0,  0]
[ 0,  0,  0]
[-1,  0,  0]
[ 1, -1,  0]
[ 0, -1,  0]
[-1, -1,  0]
[ 1,  1, -1]
[ 0,  1, -1]
[-1,  1, -1]
[ 1,  0, -1]
[ 0,  0, -1]
[-1,  0, -1]
[ 1, -1, -1]
[ 0, -1, -1]
[-1, -1, -1]

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