递归遍历数组的所有排列 [英] Go through all permutations of an array recursively

问题描述

我正在尝试编写一个递归函数以产生数组的所有排列.

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

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

It's invoked as testPermu(0) and should produce all permutations, however that does not work. How can I fix it?

它必须是递归的，每次调用该函数时，都应该获得新的排列.

It needs to be recursive, each time the function is invoked, it should get a fresh permutation.

现在的输出是

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

我正在用Java编写它，但是只要不使用Java中没有的一些库技巧，我就会理解用C，javascript或其他语言编写的示例.

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.

推荐答案

以下是完整示例:

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

这篇关于递归遍历数组的所有排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！