递归地遍历数组的所有排列

Question

我正在尝试编写一个递归函数来生成数组的所有排列。

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;
    }
}

它被调用为 testPermu(0) 并且应该产生所有排列，但是这不起作用。我该如何解决？

它需要递归，每次调用函数时，它应该得到一个新的排列。

现在的输出是

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

您可以看到许多排列缺失。

我正在用 Java 编写它，但我会理解 C 中的示例，javascript 或其他任何东西，只要它不使用 Java 中不可用的一些库技巧.

Answer 1

下面算法如何（伪代码给出）

iterate over elements:
   pick one of the element at random 
   call function again on the remaining elements
   if elements.size == 1 
       return or print

这应该在每个运行处产生一个有效的排列。如果你想要所有可能的排列，只是边迭代边累加，那么你应该有所有的排列。

Answer 2

试试

testPermu(start + 1);

Answer 3

另一种方法：

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;
    }
}

该方法首先选择一个元素，移除它并得到一个子列表，然后产生一个子列表的排列，直到列表大小变为1。

Answer 4

需要三个更正才能起作用：

仅在 (start == permus.length-1) 时打印，否则你会看到重复项
从 i = start 开始 for 循环，而不是 i = start + 1
递归调用 testPermu(start + 1); 而不是 testPermu(i);

Answer 5

不需要递归就可以做到

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;      
}

Answer 6

这是一个完整的例子：

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);
    }
}

Answer 7

@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);
}

Answer 8

我喜欢@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;
}

如果您希望按升序排列，请在将列表传递给 getPermutations() 函数之前对其进行排序。

递归地遍历数组的所有排列

Go through all permutations of an array recursively

java

algorithm

permutation