2

我有一个整数数组，需要使用 Java 找到这些元素的所有可能排列。所以我将在最后有一个包含数组的数组，其中每个数组都是原始单个数组的排列。它必须适用于任何大小的数组。

我可以为字符串执行此操作，但数组让我绊倒了。我的元素是整数，所以我不能使用简单的字符串方法，例如，如果我的整数是 1、2、14，我将置换字符串 1214。是否可以操作字符串并置换它，然后得到最后通过某种方式过滤我所需的排列？

我环顾四周，似乎找到了一些算法，但实际上所有这些都只是大量代码，几乎没有解释，所以我无法理解它们。有没有人有一个算法，一个解释过的算法！？

这是我的字符串算法：

static String[] getPermutations( String str ) { 
List<String> perms = new ArrayList<>();
    permute( "", str, perms );
    String[] list = perms.toArray( new String[ perms.size() ] );
    return list;
}

// This function recursively calls itself
static void permute( String prefix, String str, List<String> perms ) {
        int n = str.length();
        if ( n == 0 ) {
        perms.add(prefix);
        } else {
            for ( int i = 0; i < n; i++ ) {
            permute( prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), perms );
        }
    }
}
4

1 回答 1

0

permute 方法是这样的。显然，必须对 getPermutations 方法进行相关更改。逻辑实际上与 String 示例相同。

static void permute( List<Integer> prefix, List<Integer> ints, List<List<Integer>> perms ) {
        int n = ints.size();
        if ( n == 0 ) {
        perms.add(prefix);
        } else {
            for ( int i = 0; i < n; i++ ) {
                List<Integer> newPrefix = new ArrayList<Integer>();
                List<Integer> newInts = new ArrayList<Integer>();
                Collections.copy(prefix, newPrefix);
                Collections.copy(ints, newInts);

                newPrefix.add(ints.get(i));
                newInts.remove(i);

                permute( newPrefix, str.substring(0, i) + str.substring(i+1, n), perms );
            }
        }
}

如果您是效率的坚持者，那么您知道所有列表的最终大小是多少，并且您知道排列列表的最终大小是多少（N！）然后您可以使用数组，并使用以下方法保存整数到目前为止，您在阵列中的位置。但是这个解决方案是最容易理解和实施的

于 2013-10-08T19:34:03.853 回答