在本教程中，我们将看到如何在Java中查找数组的所有排列。

问题1

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

例如：

阵列：[10,20,30]

排列有：

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

解决方案

我们可以在递归的帮助下解决问题。
解释递归很难，所以我创建了一个递归树来展示它。

这是代码相同。

package org.igi.theitroad;
 
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个分支。

问题2.

给定的整数数组(可以包含重复项)，打印阵列的所有排列。

解决方案

我们可以使用递归来解决此问题，但需要处理重复项。
我们将对阵列进行排序，因此所有重复项都将被聚集。

package org.igi.theitroad;
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public class PermuteArrayWithDuplicates {
 
	public static void main(String[] args) {
		PermuteArrayWithDuplicates pa=new PermuteArrayWithDuplicates();
		
		int[] arr= {10, 20, 10};
		
		List<List<Integer>> permute = pa.permute(arr);
		
		System.out.println("Permuations of array : [10, 20, 10] 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<>();
		Arrays.sort(arr);
		permuteHelper(list, new ArrayList<>(), arr,new boolean[arr.length]);
		return list;
	}
 
	private void permuteHelper(List<List<Integer>> list, List<Integer> resultList, int [] arr, boolean [] used){
		
		//Base case
		if(resultList.size() == arr.length){
	        list.add(new ArrayList<>(resultList));
	    } else{
	        for(int i = 0; i < arr.length; i++){
	            if(used[i] || i > 0 && arr[i] == arr[i-1] && !used[i - 1]) 
	            {   
	            	    //If element is already used
	            		continue;
	            }
	            //choose element
	            used[i] = true; 
	            resultList.add(arr[i]);
	            
	            //Explore
	            permuteHelper(list, resultList, arr, used);
	            
	            //Unchoose element
	            used[i] = false; 
	            resultList.remove(resultList.size() - 1);
	        }
	    }
	}
 
}

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