Java中整数数组的排列算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/20906214/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
提示：将鼠标放在中文语句上可以显示对应的英文。显示中英文
时间：2020-08-13 05:13:04 来源:igfitidea点击:
Permutation algorithm for array of integers in Java
提问by ppalancica
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;
}
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:
我试图实现相同的功能，但返回 ArrayList，并获取 int[] 作为参数。我正在递归地执行此操作，如下所示：
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;
}
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 }:
当传递大小为 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
Please give me some advice if you encountered these issues before.
如果您以前遇到过这些问题，请给我一些建议。
Thanks in advance!
提前致谢！
回答by johk95
I've written that code some time ago, and edited a bit to match your requests. I hope it works.
我前段时间编写了该代码，并进行了一些编辑以符合您的要求。我希望它有效。
static ArrayList<String> permutations(String s) {
ArrayList<String> ret = new ArrayList<String>();
permutation(s.toCharArray(), 0, ret);
return ret;
}
public static void permutation(char[] arr, int pos, ArrayList<String> 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
I just tried it on ideone.com. It seems to work. You're welcome. :)
更新
我刚刚在ideone.com上尝试过。它似乎工作。别客气。:)
UPDATE 2
It should basically be the same code with arrays of int's:
更新 2
它应该基本上是与 int 数组相同的代码：
static ArrayList<int[]> permutations(int[] a) {
ArrayList<int[]> ret = new ArrayList<int[]>();
permutation(a, 0, ret);
return ret;
}
public static void permutation(int[] arr, int pos, ArrayList<int[]> 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;
}
UPDATE 3
Works with int's too: http://ideone.com/jLpZow
更新 3 也
适用于 int：http: //ideone.com/jLpZow
回答by MT0
import java.util.ArrayList;
import java.util.Arrays;
public class Answer {
static <E> String arrayToString( E[] arr ) {
final StringBuffer str = new StringBuffer();
for ( E e : arr )
str.append( e.toString() );
return str.toString();
}
static <E> ArrayList<E[]> permutations(E[] arr) {
final ArrayList<E[]> resultList = new ArrayList<E[]>();
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<E[]> 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<String> 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<Character[]> perms = permutations(c);
final ArrayList<String> resultList = new ArrayList<String>( perms.size() );
for ( Character[] p : perms )
{
resultList.add( arrayToString( p ) );
}
return resultList;
}
public static void main(String[] args) {
ArrayList<String> str_perms = permutations( "abc" );
for ( String p : str_perms ) System.out.println( p );
ArrayList<Integer[]> int_perms = permutations( new Integer[]{ 1, 2, 3, 4 } );
for ( Integer[] p : int_perms ) System.out.println( arrayToString( p ) );
}
}
回答by Kushtrim
This code takes String elements, but can me modified to work for integers:
此代码采用 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<String> permutations = g.generatePermutations(elements);
for ( String s : permutations)
{
System.out.println(s);
}
//System.out.println(permutations.get(999999));
}
private ArrayList<String> generatePermutations( String[] elements )
{
ArrayList<String> permutations = new ArrayList<String>();
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<String> k2 = generatePermutations(elements2);
for( String x : k2 )
{
String s = elements[i]+x;
permutations.add(s);
}
}
}
return permutations;
}
}
回答by 9 Digit Dev
By adding a TreeSet it removes duplicates and sorts the permutations.
通过添加 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<String> 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<String> generatePermutations( String[] elements )
{
ArrayList<String> permutations = new ArrayList<String>();
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<String> k2 = generatePermutations(elements2);
for( String x : k2 )
{
String s = elements[i]+x;
permutations.add(s);
}
}
}
return permutations;
}
}
回答by bobbyberg
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!
下面是一个包含使用泛型的解决方案的类。API 与您指定的有所不同，但要灵活得多。用例子最容易看到。请注意，输入的约束可能比我在这里检查的要多！
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;
}
}
Example Usage
示例用法
Calling Permutations.get(2, Integer.class, 1, 0, -1);will return the following list of integer arrays:
调用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]
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:
调用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]
回答by PixelsTech
Here you go, the below sample code uses the recursive method to get the permutation. It is generic and you can specify the output location as you like. One bonus is you can specify delimiter as well.
好了，下面的示例代码使用递归方法来获取排列。它是通用的，您可以根据需要指定输出位置。一个好处是您也可以指定分隔符。
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 <T> List<T[]> permute(T[] arr){
List<T[]> result = new ArrayList<T[]>();
permute(new ArrayList<T>(), Arrays.asList(arr), result);
return result;
}
//This is the actual method doing the permutation
private static <T> void permute(List<T> pre, List<T> cur, List<T[]> out){
int size = cur.size();
if(size == 0){
out.add((T[])pre.toArray());
} else {
for(int i=0; i<size; ++i){
List<T> tmpPre = new ArrayList<T>(pre);
List<T> tmpCur = new ArrayList<T>(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 <T> void print(List<T[]> 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, ' ');
}
}
回答by YashM
/**
*
* @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 <code>if (suffix.length == 1)</code> will print
* the only possible combination of suffix and return for computing next
* combination.
*
*
* The part after <code>if (suffix.length == 1)</code> is reached if suffix
* length is not 1 that is there may be many possible combination of suffix
* therefore make a <code>newSuffix</code> which will have suffix length
* <code>(suffix.length - 1)</code> and recursively compute the possible
* combination of this new suffix and also the original suffix prefix
* positioned by <code>startIndex</code> will change by increasing its value
* by one <code>(startIndex + 1) % suffix.length</code>
*
*
* 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;
}
}
回答by Karol Król
Here is my solution (gist):
这是我的解决方案（要点）：
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<List<Integer>> 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<int[]> 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<int[]> {
private List<List<Integer>> result = new ArrayList<>();
@Override
public void accept(int[] ints) {
result.add(IntStream.of(ints).boxed().collect(Collectors.toList()));
}
public List<List<Integer>> getResult() {
return result;
}
}
}
回答by Bob Sheehan
//Here is a recursive version that was not to hard to commit to human memory ! O(n!) permutations.
//这是一个递归版本，不难让人记忆！O(n!) 排列。
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;
}
