Java打印字符串的所有排列

左手的ㄟ右手 2023-10-05 00:49 8阅读 0赞

**问题：**编写一个Java程序以打印字符串的所有排列

**例子：**

<table style="margin-left:-20px;"> 
 <tbody> 
  <tr> 
   <td style="text-align:left;vertical-align:top;"> 
    <div style="margin-left:0px;"> 
     <div style="margin-left:0px;"> 
      <span style="color:#1c1c1c;"><span style="color:#aaaaaa;">1</span></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#1c1c1c;"><span style="color:#aaaaaa;">2</span></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#1c1c1c;"><span style="color:#aaaaaa;">3</span></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#1c1c1c;"><span style="color:#aaaaaa;">4</span></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#1c1c1c;"><span style="color:#aaaaaa;">5</span></span> 
     </div> 
    </div> </td> 
   <td style="text-align:left;vertical-align:top;"> 
    <div style="margin-left:0px;"> 
     <div style="margin-left:0px;"> 
      <span style="color:#1c1c1c;"><span style="color:#000000;">Input:&nbsp;&nbsp;lol</span></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#1c1c1c;"><span style="color:#000000;">Output: lol, llo, oll</span></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#1c1c1c;"><span style="color:#000000;">&nbsp;</span></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#1c1c1c;"><span style="color:#000000;">Input:&nbsp;&nbsp;hat</span></span> 
     </div> 
     <div style="margin-left:0px;"> 
      <span style="color:#1c1c1c;"><span style="color:#000000;">Output: hat, aht, ath, hta, tha, tah</span></span> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

解决此问题的最佳方法是使用递归，因为字符串的一部分本身就是可以重新排列以形成各种排列的字符串。

**例子：**

为了形成给定字符串的所有可能排列，我们从字符串中一个接一个地提取字符（使用循环），然后将它们附加到另一个字符串（`perm`）。

然后，我们对字符串中的其余字符递归地重复上述过程，直到没有剩余字符为止。

![使用递归对字符串进行置换][ec33474a5850138ae3f25f1ed7f62c4a.png]

当字符串中没有剩余字符时，我们将根据排列后的排列是否唯一来输出形成的排列（以前没有发生过）。

这是实现逻辑的Java程序：

import java.util.List;
    import java.util.ArrayList;
    
    class Permutations {
    	// list to store the permutaions
    	static List<String> output = new ArrayList<>();
    
    	public static void main(String[] args) {
    
    		// Input a string
    
    		String unique = "123";
    		String duplicate = "112";
    
    		/*
    		 * call the permutation method with empty string as 1st and input string as the
    		 * 2nd parameter
    		 */
    		System.out.println("All Permutations of Unique: ");
    		permutation("", unique);
    		System.out.println();
    		System.out.println("All Permutations of Duplicate: ");
    		permutation("", duplicate);
    	}
    
    	public static void permutation(String perm, String word) {
    		// base condition: word is empty
    		if (word.isEmpty()) {
    			// print only if a new permutation is found
    			if (!output.contains(perm)) {
    				System.out.print(perm + " ");
    				output.add(perm);
    			}
    		}
    
    		// Loop
    		for (int i = 0; i < word.length(); i++) {
    			// split: remove the character at i from the word and append to the perm
    			String w = word.substring(0, i) + word.substring(i + 1, word.length());
    			String p = perm + word.charAt(i);
    
    			// recursive call
    			permutation(p, w);
    		}
    
    	}
    }

**输出**：

All Permutations of Unique:  
123 132 213 231 312 321  
All Permutations of Duplicate:  
112 121 211   
  
*在我们的程序中，我们将所有排列存储在列表中，以仅打印不重复的排列。*

我们还可以使用上述程序输入数字以打印其所有排列，因为它将被视为字符串。

字符串的所有排列也可以称为[anagrams][]，因此上述程序也是打印字符串的所有anagram的程序。

[ec33474a5850138ae3f25f1ed7f62c4a.png]: https://img-blog.csdnimg.cn/img_convert/ec33474a5850138ae3f25f1ed7f62c4a.png
[anagrams]: https://pencilprogrammer.com/java-programs/check-whether-two-strings-are-anagram/