java 递归遍历数组的所有排列
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/28794268/
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
Go through all permutations of an array recursively
提问by MightyPork
I am trying to write a recursive function to produce all permutations of an array.
我正在尝试编写一个递归函数来生成数组的所有排列。
static int permus[] = new int[] { 1, 2, 3, 4, 5 };
static void testPermu(int start)
{
// Print it
System.out.println(Arrays.toString(permus));
int k;
for (int i = start + 1; i < permus.length; i++) {
// swap
k = permus[start];
permus[start] = permus[i];
permus[i] = k;
testPermu(i);
// unswap
k = permus[start];
permus[start] = permus[i];
permus[i] = k;
}
}
It's invoked as testPermu(0)and should produce all permutations, however that does not work. How can I fix it?
它被调用为testPermu(0)并且应该产生所有排列，但是这不起作用。我该如何解决？
It needs to be recursive, each time the function is invoked, it should get a fresh permutation.
它需要递归，每次调用该函数时，都应该得到一个新的排列。
output now is
现在的输出是
[1, 2, 3, 4, 5] [2, 1, 3, 4, 5] [2, 3, 1, 4, 5] [2, 3, 4, 1, 5] [2, 3, 4, 5, 1] [2, 3, 5, 4, 1] [2, 4, 3, 1, 5] [2, 4, 3, 5, 1] [2, 5, 3, 4, 1] [3, 2, 1, 4, 5] [3, 2, 4, 1, 5] [3, 2, 4, 5, 1] [3, 2, 5, 4, 1] [4, 2, 3, 1, 5] [4, 2, 3, 5, 1] [5, 2, 3, 4, 1]
You can see that many of the permutations are missing.
您可以看到缺少许多排列。
I'm writing it in Java but I'll understand example in C, javascript or anything else as long as it's not using some library tricks not available in Java.
我正在用 Java 编写它，但只要不使用 Java 中不可用的一些库技巧，我就会理解 C、javascript 或其他任何示例。
采纳答案by Eric Wang
Here is a full example:
这是一个完整的例子：
package eric.math;
import java.util.Arrays;
public class Permute {
// swap 2 elements of an array,
void swap(int[] arr, int x, int y) {
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
/**
* print permutations of array
* @param arr
* original int array,
*/
void permute(int[] arr) {
permute(arr, 0, arr.length - 1);
}
/**
* print permutations of array
*
* @param arr
* original int array,
* @param i
* start index
* @param n
* end index
*/
void permute(int[] arr, int i, int n) {
int j;
if (i == n)
System.out.println(Arrays.toString(arr));
else {
for (j = i; j <= n; j++) {
swap(arr, i, j);
permute(arr, i + 1, n);
swap(arr, i, j); // backtrack
}
}
}
public static void main(String[] args) {
int arr[] = { 1, 2, 3 };
new Permute().permute(arr);
}
}
回答by Miljen Mikic
Three corrections are needed in order to work:
需要三处更正才能工作：
- print only if
(start == permus.length-1), otherwise you'll see duplicates - start the
forloop fromi = start, noti = start + 1 - recursively call
testPermu(start + 1);instead oftestPermu(i);
- 仅在 if 时打印
(start == permus.length-1)，否则您会看到重复项 - 从 开始
for循环i = start，而不是i = start + 1 - 递归调用
testPermu(start + 1);而不是testPermu(i);
回答by Ankush G
@Enric solution is nice, but using solution below we can avoid 80 swaps and perform only 24 swaps.
@Enric 解决方案很好，但使用下面的解决方案我们可以避免 80 次交换并且只执行 24 次交换。
static void permutation(int[] a, int i, int j) {
for (; j < a.length && i < a.length; j++) {
int[] temp = null;
if (i != j) {
temp = swap(a, i, j);
System.out.println(Arrays.toString(temp));
}else{
temp = a;
}
permutation(temp, i + 1, i + 1);
}
}
public static void main(String[] args) {
int[] a = { 0, 1, 2, 3 };
permutation(a, 0, 0);
}
回答by tonychow0929
Another approach:
另一种方法：
static ArrayList<ArrayList<Integer>> getPermutation(ArrayList<Integer> ints) {
if (ints.size() == 1) {
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
list.add(ints);
return list;
} else {
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for (Integer i: ints) {
ArrayList<Integer> subList = new ArrayList<>(ints);
subList.remove(i);
ArrayList<ArrayList<Integer>> subListNew = getPermutation(subList);
for (ArrayList<Integer> _list: subListNew) {
ArrayList<Integer> local = new ArrayList<>();
local.add(i);
local.addAll(_list);
list.add(local);
}
}
return list;
}
}
This method first selects an element, removes it and obtains a sub-list, then produces a permutation of the sub-list until the list size becomes 1.
该方法首先选择一个元素，将其移除并获得一个子列表，然后生成子列表的排列，直到列表大小变为 1。
回答by Luka Rahne
Try with
试试
testPermu(start + 1);
回答by Oneiros
I like @tony200910041 approach but maybe someone would like a cleaner and more generic version of it:
我喜欢 @tony200910041 方法，但也许有人想要更简洁、更通用的版本：
public static <T> List<List<T>> getPermutations(List<T> list) {
if (list.size() == 1)
return Collections.singletonList(list);
List<List<T>> perms = new ArrayList<>();
for (T element: list) {
List<T> subList = new ArrayList<>(list);
subList.remove(element);
List<List<T>> subPerms = getPermutations(subList);
for (List<T> subPerm: subPerms) {
List<T> perm = new ArrayList<>();
perm.add(element);
perm.addAll(subPerm);
perms.add(perm);
}
}
return perms;
}
Sort the list before passing it to the getPermutations()function if you want your permutations in ascending order.
getPermutations()如果您希望按升序排列，请在将列表传递给函数之前对列表进行排序。
回答by Darren
You can do it simply without recursion
您可以简单地做到这一点而无需递归
public static Integer[] permutate(int i)
{
int length = permus.length;
Integer[] result = new Integer[length];
List<Integer> chosen = new ArrayList<Integer>(Arrays.asList(permus));
int divider = 1;
for (int j=2; j<length; j++)
{
divider *= j;
}
for (int j=length; j>1; j--)
{
int index = i/divider;
result[length - j] = chosen.remove(index);
i = i - divider * (i/divider);
divider = divider / (j-1);
}
result[length -1] = chosen.remove(0);
return result;
}
回答by posdef
How about the following algorithm (given in pseudocode)
下面的算法怎么样（以伪代码给出）
iterate over elements:
pick one of the element at random
call function again on the remaining elements
if elements.size == 1
return or print
This should produce a valid permutation at each run. If you want all possible permutations, just accumulate as you iterate, then you should have all permutations.
这应该在每次运行时产生一个有效的排列。如果您想要所有可能的排列，只需在迭代时累积，那么您应该拥有所有排列。
