Java中整数数组的置换算法

我有一个工作示例来生成String中的所有char排列，如下所示：

static ArrayList permutations(String s) { if (s == null) { return null; } ArrayList resultList = new ArrayList(); 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 subPermutations = permutations(subString); for (String item : subPermutations) { resultList.add(currentChar + item); } } return resultList; } 

我试图实现相同的function，但返回ArrayList，并获取int []作为参数。 我正在递归地执行此操作，如下所示：

 static ArrayList permutations(int[] arr) { ArrayList resultList = new ArrayList(); 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 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}：

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

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

提前致谢！

Answer 1

 import java.util.ArrayList; import java.util.Arrays; public class Answer { static  String arrayToString( E[] arr ) { final StringBuffer str = new StringBuffer(); for ( E e : arr ) str.append( e.toString() ); return str.toString(); } static  ArrayList permutations(E[] arr) { final ArrayList resultList = new ArrayList(); final int l = arr.length; if ( l == 0 ) return resultList; if ( l == 1 ) { resultList.add( arr ); return resultList; } E[] subClone = Arrays.copyOf( arr, l - 1); System.arraycopy( arr, 1, subClone, 0, l - 1 ); for ( int i = 0; i < l; ++i ){ E e = arr[i]; if ( i > 0 ) subClone[i-1] = arr[0]; final ArrayList subPermutations = permutations( subClone ); for ( E[] sc : subPermutations ) { E[] clone = Arrays.copyOf( arr, l ); clone[0] = e; System.arraycopy( sc, 0, clone, 1, l - 1 ); resultList.add( clone ); } if ( i > 0 ) subClone[i-1] = e; } return resultList; } static ArrayList permutations(String arr) { final Character[] c = new Character[ arr.length() ]; for ( int i = 0; i < arr.length(); ++i ) c[i] = arr.charAt( i ); final ArrayList perms = permutations(c); final ArrayList resultList = new ArrayList( perms.size() ); for ( Character[] p : perms ) { resultList.add( arrayToString( p ) ); } return resultList; } public static void main(String[] args) { ArrayList str_perms = permutations( "abc" ); for ( String p : str_perms ) System.out.println( p ); ArrayList int_perms = permutations( new Integer[]{ 1, 2, 3, 4 } ); for ( Integer[] p : int_perms ) System.out.println( arrayToString( p ) ); } } 

Answer 2

此代码采用String元素，但我可以修改为适用于整数：

 import java.util.*; /** * Write a description of class GeneratePermutations here. * * @author Kushtrim * @version 1.01 */ public class GeneratePermutations { public static void main(String args[]) { GeneratePermutations g = new GeneratePermutations(); String[] elements = {"a","b","c",}; ArrayList permutations = g.generatePermutations(elements); for ( String s : permutations) { System.out.println(s); } //System.out.println(permutations.get(999999)); } private ArrayList generatePermutations( String[] elements ) { ArrayList permutations = new ArrayList(); if ( elements.length == 2 ) { String x1 = elements[0] + elements[1]; String x2 = elements[1] + elements[0]; permutations.add(x1); permutations.add(x2); } else { for ( int i = 0 ; i < elements.length ; i++) { String[] elements2 = new String[elements.length -1]; int kalo = 0; for( int j =0 ; j< elements2.length ; j++ ) { if( i == j) { kalo = 1; } elements2[j] = elements[j+kalo]; } ArrayList k2 = generatePermutations(elements2); for( String x : k2 ) { String s = elements[i]+x; permutations.add(s); } } } return permutations; } } 

Answer 3

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

 public static final class Permutations { private Permutations() {} public static  List get(Class itemClass, T... itemsPool) { return get(itemsPool.length, itemClass, itemsPool); } public static  List get(int size, Class itemClass, T... itemsPool) { if (size < 1) { return new ArrayList(); } int itemsPoolCount = itemsPool.length; List permutations = new ArrayList(); 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); 将返回以下整数数组列表：

 [ 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 ：

 [ 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] 

Answer 4

//这是一个递归版本，并不难以承诺人类记忆！ O（n！）排列。

 public static Set getPermutationsRecursive(Integer[] num){ if (num == null) return null; Set 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 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; } 

Answer 5

 /** * * @param startIndex is the position of the suffix first element * @param prefix is the prefix of the pattern * @param suffix is the suffix of the pattern, will determine the complexity * permute method. * * * The block if (suffix.length == 1) will print * the only possible combination of suffix and return for computing next * combination. * * * The part after if (suffix.length == 1) is reached if suffix * length is not 1 that is there may be many possible combination of suffix * therefore make a newSuffix which will have suffix length * (suffix.length - 1) and recursively compute the possible * combination of this new suffix and also the original suffix prefix * positioned by startIndex will change by increasing its value * by one (startIndex + 1) % suffix.length * * * T(N) = N * T(N - 1) + N * = N! + N!(1 + 1/N + 1/(N * (N - 1)) + ... + 1/N!) * * */ public static void permute(int startIndex, int prefix[], int suffix[]) { if (suffix.length == 1) { for (int i = 0; i < prefix.length; i++) { System.out.print(prefix[i] + " "); } System.out.print(suffix[0]); System.out.println(" "); return; } for (int i = 0; i < suffix.length; i++) { counter++; int newPrefix[] = new int[prefix.length + 1]; System.arraycopy(prefix, 0, newPrefix, 0, prefix.length); newPrefix[prefix.length] = suffix[startIndex]; int newSuffix[] = new int[suffix.length - 1]; for (int j = 1; j < suffix.length; j++) { newSuffix[j - 1] = suffix[(startIndex + j) % suffix.length]; } permute((startIndex % newSuffix.length), newPrefix, newSuffix); startIndex = (startIndex + 1) % suffix.length; } } 

Answer 6

我前段时间写过这段代码，并编辑了一下以符合您的要求。 我希望它有效。

 static ArrayList permutations(String s) { ArrayList ret = new ArrayList(); permutation(s.toCharArray(), 0, ret); return ret; } public static void permutation(char[] arr, int pos, ArrayList list){ if(arr.length - pos == 1) list.add(new String(arr)); else for(int i = pos; i < arr.length; i++){ swap(arr, pos, i); permutation(arr, pos+1, list); swap(arr, pos, i); } } public static void swap(char[] arr, int pos1, int pos2){ char h = arr[pos1]; arr[pos1] = arr[pos2]; arr[pos2] = h; } 

UPDATE
我刚刚在ideone.com上试过了 。 它似乎工作。 别客气。 🙂

更新2
它应该与int的数组基本相同：

 static ArrayList permutations(int[] a) { ArrayList ret = new ArrayList(); permutation(a, 0, ret); return ret; } public static void permutation(int[] arr, int pos, ArrayList list){ if(arr.length - pos == 1) list.add(arr.clone()); else for(int i = pos; i < arr.length; i++){ swap(arr, pos, i); permutation(arr, pos+1, list); swap(arr, pos, i); } } public static void swap(int[] arr, int pos1, int pos2){ int h = arr[pos1]; arr[pos1] = arr[pos2]; arr[pos2] = h; } 

更新3
也适用于int： http ： //ideone.com/jLpZow

Answer 7

通过添加TreeSet，它可以删除重复项并对排列进行排序。

---

 package permutations; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Scanner; import java.util.TreeSet; public class Permutations { public static void main(String args[]) { Scanner scanner = new Scanner(new InputStreamReader(System.in)); System.out.println("This application accepts input of a string and creates a list of all possible permutations\n\r"); System.out.println("Please Enter a string of characters"); String input = scanner.nextLine(); String[] elements = input.split(""); Permutations g = new Permutations(); ArrayList permutations = g.generatePermutations(elements); TreeSet ts = new TreeSet(); for ( String s : permutations) { //System.out.println(s); ts.add(s); } System.out.println("List of all possible permutations"); System.out.println(ts); } private ArrayList generatePermutations( String[] elements ) { ArrayList permutations = new ArrayList(); if ( elements.length == 2 ) { String x1 = elements[0] + elements[1]; String x2 = elements[1] + elements[0]; permutations.add(x1); permutations.add(x2); } else { for ( int i = 0 ; i < elements.length ; i++) { String[] elements2 = new String[elements.length -1]; int kalo = 0; for( int j =0 ; j< elements2.length ; j++ ) { if( i == j) { kalo = 1; } elements2[j] = elements[j+kalo]; } ArrayList k2 = generatePermutations(elements2); for( String x : k2 ) { String s = elements[i]+x; permutations.add(s); } } } return permutations; } } 

Answer 8

在这里，下面的示例代码使用递归方法来获得排列。 它是通用的，您可以根据需要指定输出位置。 一个好处是你也可以指定分隔符。

 import java.io.FileNotFoundException; import java.io.OutputStream; import java.io.PrintStream; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Permutation { //The entry of the permutation method public static  List permute(T[] arr){ List result = new ArrayList(); permute(new ArrayList(), Arrays.asList(arr), result); return result; } //This is the actual method doing the permutation private static  void permute(List pre, List cur, List out){ int size = cur.size(); if(size == 0){ out.add((T[])pre.toArray()); } else { for(int i=0; i tmpPre = new ArrayList(pre); List tmpCur = new ArrayList(cur); tmpPre.add(cur.get(i)); tmpCur.remove((T)cur.get(i)); permute(tmpPre, tmpCur, out); } } } //Print each row of the permutated values private static  void print(List list, OutputStream out, char delim){ try{ for(T[] i : list){ int count = 0; for(T t : i){ if(++count == i.length){ out.write((t.toString()).getBytes()); } else{ out.write((t.toString()+delim).getBytes()); } } out.write("\n".getBytes()); } } catch (Exception ex){ ex.printStackTrace(); } } public static void main(String[] args) throws FileNotFoundException { Integer[] ints = new Integer[] {1, 2, 3, 4}; Permutation.print(Permutation.permute(ints), System.out, ','); Character[] chars = {'a', 'b', 'c', 'd', 'e'}; Permutation.print(Permutation.permute(chars), new PrintStream("permute.txt"), ' '); String[] strs = {"abc", "123"}; Permutation.print(Permutation.permute(strs), System.err, ' '); } } 

Answer 9

这是我的解决方案（ 要点 ）：

 import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.function.Consumer; import java.util.stream.Collectors; import java.util.stream.IntStream; /** * @author Karol Krol */ public class Permutation { private Permutation() { } public static List> permutation(final int[] numbers) { final PermutationCollector permutationCollector = new PermutationCollector(); permutation(new int[0], numbers, permutationCollector); return permutationCollector.getResult(); } private static void permutation(int[] prefix, int[] array, final Consumer operation) { int length = array.length; if (length == 0) { operation.accept(prefix); } else { for (int i = 0; i < length; ++i) { final int[] newPrefix = append(prefix, array[i]); final int[] reducedArray = reduce(array, i); permutation(newPrefix, reducedArray, operation); } } } private static int[] append(int[] array, int element) { int newLength = array.length + 1; array = Arrays.copyOf(array, newLength); array[newLength - 1] = element; return array; } private static int[] reduce(int[] array, int index) { final int newLength = array.length - 1; if (index == 0) { return Arrays.copyOfRange(array, 1, array.length); } else { final int[] dest = new int[newLength]; System.arraycopy(array, 0, dest, 0, index); System.arraycopy(array, index + 1, dest, index, newLength - index); return dest; } } public static class PermutationCollector implements Consumer { private List> result = new ArrayList<>(); @Override public void accept(int[] ints) { result.add(IntStream.of(ints).boxed().collect(Collectors.toList())); } public List> getResult() { return result; } } }