Java数组全排列

末蓝、 2023-10-05 21:01 1阅读 0赞

##  ##

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

--------------------

### **问题1** ###

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

例如：

数组：\[10，20，30\]

排列是：

\[10，20，30\] \[10，30，20\] \[20，10，30\] \[20，30，10\] \[30，10，20\] \[30，20，10\]

--------------------

### **解决方案** ###

我们可以借助递归来解决问题。解释递归非常困难，因此我创建了一个递归树来演示它。

这是相同的代码。

<table style="margin-left:-29px;"> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> 
 <div style="margin-left:0px;"> 
 <div style="margin-left:0px;"> 
 1 
 </div> 
 <div style="margin-left:0px;"> 
 2 
 </div> 
 <div style="margin-left:0px;"> 
 3 
 </div> 
 <div style="margin-left:0px;"> 
 4 
 </div> 
 <div style="margin-left:0px;"> 
 5 
 </div> 
 <div style="margin-left:0px;"> 
 6 
 </div> 
 <div style="margin-left:0px;"> 
 7 
 </div> 
 <div style="margin-left:0px;"> 
 8 
 </div> 
 <div style="margin-left:0px;"> 
 9 
 </div> 
 <div style="margin-left:0px;"> 
 10 
 </div> 
 <div style="margin-left:0px;"> 
 11 
 </div> 
 <div style="margin-left:0px;"> 
 12 
 </div> 
 <div style="margin-left:0px;"> 
 13 
 </div> 
 <div style="margin-left:0px;"> 
 14 
 </div> 
 <div style="margin-left:0px;"> 
 15 
 </div> 
 <div style="margin-left:0px;"> 
 16 
 </div> 
 <div style="margin-left:0px;"> 
 17 
 </div> 
 <div style="margin-left:0px;"> 
 18 
 </div> 
 <div style="margin-left:0px;"> 
 19 
 </div> 
 <div style="margin-left:0px;"> 
 20 
 </div> 
 <div style="margin-left:0px;"> 
 21 
 </div> 
 <div style="margin-left:0px;"> 
 22 
 </div> 
 <div style="margin-left:0px;"> 
 23 
 </div> 
 <div style="margin-left:0px;"> 
 24 
 </div> 
 <div style="margin-left:0px;"> 
 25 
 </div> 
 <div style="margin-left:0px;"> 
 26 
 </div> 
 <div style="margin-left:0px;"> 
 27 
 </div> 
 <div style="margin-left:0px;"> 
 28 
 </div> 
 <div style="margin-left:0px;"> 
 29 
 </div> 
 <div style="margin-left:0px;"> 
 30 
 </div> 
 <div style="margin-left:0px;"> 
 31 
 </div> 
 <div style="margin-left:0px;"> 
 32 
 </div> 
 <div style="margin-left:0px;"> 
 33 
 </div> 
 <div style="margin-left:0px;"> 
 34 
 </div> 
 <div style="margin-left:0px;"> 
 35 
 </div> 
 <div style="margin-left:0px;"> 
 36 
 </div> 
 <div style="margin-left:0px;"> 
 37 
 </div> 
 <div style="margin-left:0px;"> 
 38 
 </div> 
 <div style="margin-left:0px;"> 
 39 
 </div> 
 <div style="margin-left:0px;"> 
 40 
 </div> 
 <div style="margin-left:0px;"> 
 41 
 </div> 
 <div style="margin-left:0px;"> 
 42 
 </div> 
 <div style="margin-left:0px;"> 
 43 
 </div> 
 <div style="margin-left:0px;"> 
 44 
 </div> 
 <div style="margin-left:0px;"> 
 45 
 </div> 
 <div style="margin-left:0px;"> 
 46 
 </div> 
 <div style="margin-left:0px;"> 
 47 
 </div> 
 <div style="margin-left:0px;"> 
 48 
 </div> 
 <div style="margin-left:0px;"> 
 49 
 </div> 
 <div style="margin-left:0px;"> 
 50 
 </div> 
 <div style="margin-left:0px;"> 
 51 
 </div> 
 <div style="margin-left:0px;"> 
 52 
 </div> 
 <div style="margin-left:0px;"> 
 53 
 </div> 
 <div style="margin-left:0px;"> 
 54 
 </div> 
 <div style="margin-left:0px;"> 
 55 
 </div> 
 </div> </td> 
 <td style="vertical-align:top;width:696px;"> 
 <div style="margin-left:0px;"> 
 <div style="margin-left:0px;"> 
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 package org.arpit.java2blog; 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 import java.util.ArrayList; 
 </div> 
 <div style="margin-left:0px;"> 
 import java.util.List; 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 public class PermutateArray { 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 public static void main(String[] args) { 
 </div> 
 <div style="margin-left:0px;"> 
 PermutateArray pa=new PermutateArray(); 
 </div> 
 <div style="margin-left:0px;">
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 int[] arr= { 10, 20, 30}; 
 </div> 
 <div style="margin-left:0px;">
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 List&lt;List&lt;Integer&gt;&gt; permute = pa.permute(arr); 
 </div> 
 <div style="margin-left:0px;">
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 System.out.println("Permuations of array : [10, 20, 30] are:"); 
 </div> 
 <div style="margin-left:0px;"> 
 System.out.println("========================================="); 
 </div> 
 <div style="margin-left:0px;"> 
 for(List&lt;Integer&gt; perm:permute) 
 </div> 
 <div style="margin-left:0px;"> 
 { 
 </div> 
 <div style="margin-left:0px;"> 
 System.out.println(perm); 
 </div> 
 <div style="margin-left:0px;"> 
 } 
 </div> 
 <div style="margin-left:0px;">
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 } 
 </div> 
 <div style="margin-left:0px;"> 
 public List&lt;List&lt;Integer&gt;&gt; permute(int[] arr) { 
 </div> 
 <div style="margin-left:0px;"> 
 List&lt;List&lt;Integer&gt;&gt; list = new ArrayList&lt;&gt;(); 
 </div> 
 <div style="margin-left:0px;"> 
 permuteHelper(list, new ArrayList&lt;&gt;(), arr); 
 </div> 
 <div style="margin-left:0px;"> 
 return list; 
 </div> 
 <div style="margin-left:0px;"> 
 } 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 private void permuteHelper(List&lt;List&lt;Integer&gt;&gt; list, List&lt;Integer&gt; resultList, int [] arr){ 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 // Base case 
 </div> 
 <div style="margin-left:0px;"> 
 if(resultList.size() == arr.length){ 
 </div> 
 <div style="margin-left:0px;"> 
 list.add(new ArrayList&lt;&gt;(resultList)); 
 </div> 
 <div style="margin-left:0px;"> 
 } 
 </div> 
 <div style="margin-left:0px;"> 
 else{ 
 </div> 
 <div style="margin-left:0px;"> 
 for(int i = 0; i &lt; arr.length; i++){ 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 if(resultList.contains(arr[i])) 
 </div> 
 <div style="margin-left:0px;"> 
 { 
 </div> 
 <div style="margin-left:0px;"> 
 // If element already exists in the list then skip 
 </div> 
 <div style="margin-left:0px;"> 
 continue; 
 </div> 
 <div style="margin-left:0px;"> 
 } 
 </div> 
 <div style="margin-left:0px;"> 
 // Choose element 
 </div> 
 <div style="margin-left:0px;"> 
 resultList.add(arr[i]); 
 </div> 
 <div style="margin-left:0px;"> 
 // Explore 
 </div> 
 <div style="margin-left:0px;"> 
 permuteHelper(list, resultList, arr); 
 </div> 
 <div style="margin-left:0px;"> 
 // Unchoose element 
 </div> 
 <div style="margin-left:0px;"> 
 resultList.remove(resultList.size() - 1); 
 </div> 
 <div style="margin-left:0px;"> 
 } 
 </div> 
 <div style="margin-left:0px;"> 
 } 
 </div> 
 <div style="margin-left:0px;"> 
 } 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 } 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp; 
 </div> 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

当您在程序上方运行时，将获得以下输出：

数组的排列：\[10，20，30\]是：  
====================================== ====  
\[10，20，30\] \[ 10，30，20 \] \[ 20，10，30 \] \[ 20，30，10 \] \[ 30，10，20 \] \[ 30，20，10 \]

我已经用下图说明了递归在这里的工作方式。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI_size_16_color_FFFFFF_t_70][]  
您需要在新窗口中打开该图并进行缩放。

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

--------------------

### **问题2** ###

给定整数数组（可以包含重复项），请打印该数组的所有排列。

--------------------

### **解决方案** ###

我们也可以使用递归来解决这个问题，但需要照顾重复项。我们将对数组进行排序，因此所有重复项都是连续的。

<table style="margin-left:-29px;"> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> 
 <div style="margin-left:0px;"> 
 <div style="margin-left:0px;"> 
 1 
 </div> 
 <div style="margin-left:0px;"> 
 2 
 </div> 
 <div style="margin-left:0px;"> 
 3 
 </div> 
 <div style="margin-left:0px;"> 
 4 
 </div> 
 <div style="margin-left:0px;"> 
 5 
 </div> 
 <div style="margin-left:0px;"> 
 6 
 </div> 
 <div style="margin-left:0px;"> 
 7 
 </div> 
 <div style="margin-left:0px;"> 
 8 
 </div> 
 <div style="margin-left:0px;"> 
 9 
 </div> 
 <div style="margin-left:0px;"> 
 10 
 </div> 
 <div style="margin-left:0px;"> 
 11 
 </div> 
 <div style="margin-left:0px;"> 
 12 
 </div> 
 <div style="margin-left:0px;"> 
 13 
 </div> 
 <div style="margin-left:0px;"> 
 14 
 </div> 
 <div style="margin-left:0px;"> 
 15 
 </div> 
 <div style="margin-left:0px;"> 
 16 
 </div> 
 <div style="margin-left:0px;"> 
 17 
 </div> 
 <div style="margin-left:0px;"> 
 18 
 </div> 
 <div style="margin-left:0px;"> 
 19 
 </div> 
 <div style="margin-left:0px;"> 
 20 
 </div> 
 <div style="margin-left:0px;"> 
 21 
 </div> 
 <div style="margin-left:0px;"> 
 22 
 </div> 
 <div style="margin-left:0px;"> 
 23 
 </div> 
 <div style="margin-left:0px;"> 
 24 
 </div> 
 <div style="margin-left:0px;"> 
 25 
 </div> 
 <div style="margin-left:0px;"> 
 26 
 </div> 
 <div style="margin-left:0px;"> 
 27 
 </div> 
 <div style="margin-left:0px;"> 
 28 
 </div> 
 <div style="margin-left:0px;"> 
 29 
 </div> 
 <div style="margin-left:0px;"> 
 30 
 </div> 
 <div style="margin-left:0px;"> 
 31 
 </div> 
 <div style="margin-left:0px;"> 
 32 
 </div> 
 <div style="margin-left:0px;"> 
 33 
 </div> 
 <div style="margin-left:0px;"> 
 34 
 </div> 
 <div style="margin-left:0px;"> 
 35 
 </div> 
 <div style="margin-left:0px;"> 
 36 
 </div> 
 <div style="margin-left:0px;"> 
 37 
 </div> 
 <div style="margin-left:0px;"> 
 38 
 </div> 
 <div style="margin-left:0px;"> 
 39 
 </div> 
 <div style="margin-left:0px;"> 
 40 
 </div> 
 <div style="margin-left:0px;"> 
 41 
 </div> 
 <div style="margin-left:0px;"> 
 42 
 </div> 
 <div style="margin-left:0px;"> 
 43 
 </div> 
 <div style="margin-left:0px;"> 
 44 
 </div> 
 <div style="margin-left:0px;"> 
 45 
 </div> 
 <div style="margin-left:0px;"> 
 46 
 </div> 
 <div style="margin-left:0px;"> 
 47 
 </div> 
 <div style="margin-left:0px;"> 
 48 
 </div> 
 <div style="margin-left:0px;"> 
 49 
 </div> 
 <div style="margin-left:0px;"> 
 50 
 </div> 
 <div style="margin-left:0px;"> 
 51 
 </div> 
 <div style="margin-left:0px;"> 
 52 
 </div> 
 <div style="margin-left:0px;"> 
 53 
 </div> 
 <div style="margin-left:0px;"> 
 54 
 </div> 
 <div style="margin-left:0px;"> 
 55 
 </div> 
 <div style="margin-left:0px;"> 
 56 
 </div> 
 <div style="margin-left:0px;"> 
 57 
 </div> 
 <div style="margin-left:0px;"> 
 58 
 </div> 
 <div style="margin-left:0px;"> 
 59 
 </div> 
 </div> </td> 
 <td style="vertical-align:top;width:696px;"> 
 <div style="margin-left:0px;"> 
 <div style="margin-left:0px;"> 
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 package org.arpit.java2blog; 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 import java.util.ArrayList; 
 </div> 
 <div style="margin-left:0px;"> 
 import java.util.Arrays; 
 </div> 
 <div style="margin-left:0px;"> 
 import java.util.List; 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 public class PermuteArrayWithDuplicates { 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 public static void main(String[] args) { 
 </div> 
 <div style="margin-left:0px;"> 
 PermuteArrayWithDuplicates pa=new PermuteArrayWithDuplicates(); 
 </div> 
 <div style="margin-left:0px;">
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 int[] arr= { 10, 20, 10}; 
 </div> 
 <div style="margin-left:0px;">
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 List&lt;List&lt;Integer&gt;&gt; permute = pa.permute(arr); 
 </div> 
 <div style="margin-left:0px;">
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 System.out.println("Permuations of array : [10, 20, 10] are:"); 
 </div> 
 <div style="margin-left:0px;"> 
 System.out.println("========================================="); 
 </div> 
 <div style="margin-left:0px;"> 
 for(List&lt;Integer&gt; perm:permute) 
 </div> 
 <div style="margin-left:0px;"> 
 { 
 </div> 
 <div style="margin-left:0px;"> 
 System.out.println(perm); 
 </div> 
 <div style="margin-left:0px;"> 
 } 
 </div> 
 <div style="margin-left:0px;">
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 } 
 </div> 
 <div style="margin-left:0px;"> 
 public List&lt;List&lt;Integer&gt;&gt; permute(int[] arr) { 
 </div> 
 <div style="margin-left:0px;"> 
 List&lt;List&lt;Integer&gt;&gt; list = new ArrayList&lt;&gt;(); 
 </div> 
 <div style="margin-left:0px;"> 
 Arrays.sort(arr); 
 </div> 
 <div style="margin-left:0px;"> 
 permuteHelper(list, new ArrayList&lt;&gt;(), arr,new boolean[arr.length]); 
 </div> 
 <div style="margin-left:0px;"> 
 return list; 
 </div> 
 <div style="margin-left:0px;"> 
 } 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 private void permuteHelper(List&lt;List&lt;Integer&gt;&gt; list, List&lt;Integer&gt; resultList, int [] arr, boolean [] used){ 
 </div> 
 <div style="margin-left:0px;">
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 // Base case 
 </div> 
 <div style="margin-left:0px;"> 
 if(resultList.size() == arr.length){ 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list.add(new ArrayList&lt;&gt;(resultList)); 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp;&nbsp;&nbsp;&nbsp;} else{ 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(int i = 0; i &lt; arr.length; i++){ 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(used[i] || i &gt; 0 &amp;&amp; arr[i] == arr[i-1] &amp;&amp; !used[i - 1]) 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;// If element is already used 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; continue; 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;// choose element 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;used[i] = true; 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;resultList.add(arr[i]); 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;// Explore 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;permuteHelper(list, resultList, arr, used); 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;// Unchoose element 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;used[i] = false; 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;resultList.remove(resultList.size() - 1); 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 </div> 
 <div style="margin-left:0px;"> 
 } 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp; 
 </div> 
 <div style="margin-left:0px;"> 
 } 
 </div> 
 <div style="margin-left:0px;"> 
 &nbsp; 
 </div> 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

数组的排列：\[10，20，10\]是：  
======================================= ====  
\[ 10，10，20 \] \[ 10，20，10 \] \[ 20，10，10 \]

这就是关于Java中数组的排列的全部内容。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210303132047396.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI=,size_16,color_FFFFFF,t_70