java 中数组的排列。

Question

给定不同整数的数组，打印数组的所有排列。

例如：

array : [10, 20, 30]

Permuations are :

[10, 20, 30] [10, 30, 20] [20, 10, 30] [20, 30, 10] [30, 10, 20] [30, 20, 10]

Answer 1

我们可以借助递归来解决问题。递归很难解释，所以我创建了一个递归树来演示它。

这是相同的代码。

package org.arpit.java2blog;

import java.util.ArrayList;
import java.util.List;

public class PermutateArray {

    public static void main(String[] args) {
        PermutateArray pa=new PermutateArray();

        int[] arr= {10, 20, 30};

        List<List<Integer>> permute = pa.permute(arr);

        System.out.println("Permuations of array : [10, 20, 30] are:");
        System.out.println("=========================================");
        for(List<Integer> perm:permute)
        {
            System.out.println(perm);
        }

    }
    public List<List<Integer>> permute(int[] arr) {
        List<List<Integer>> list = new ArrayList<>();
        permuteHelper(list, new ArrayList<>(), arr);
        return list;
    }

    private void permuteHelper(List<List<Integer>> list, List<Integer> resultList, int [] arr){

        // Base case
        if(resultList.size() == arr.length){
            list.add(new ArrayList<>(resultList));
        } 
        else{
            for(int i = 0; i < arr.length; i++){ 

                if(resultList.contains(arr[i])) 
                {
                    // If element already exists in the list then skip
                    continue; 
                }
                // Choose element
                resultList.add(arr[i]);
                // Explore
                permuteHelper(list, resultList, arr);
                // Unchoose element
                resultList.remove(resultList.size() - 1);
            }
        }
    } 

}

当你运行上面的程序时，你会得到以下输出：

Permuations of array : [10, 20, 30] are:
=========================================
[10, 20, 30] [10, 30, 20] [20, 10, 30] [20, 30, 10] [30, 10, 20] [30, 20, 10]

我已经用下图说明了递归是如何在这里工作的。

您需要在新窗口中打开此图表并对其进行缩放。

由于数组中有 3 个元素，因此每个节点有 3 个分支。