字符串排列和组合的JAVA实现

男娘i 2022-09-26 02:21 186阅读 0赞

字符串的组合：

给一个字符串，比如ABC， 把所有的组合，即：A, B, C, AB, AC, BC, ABC, 都找出来。

解题思路：

假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符，我们有两种选择：一是把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符；二是不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。

字符串的排列：

**\[java\]**  [view plain][]   [copy][view plain]

1.  **public** **static** **void** combiantion(**char** chs\[\])\{  
2.      **if**(chs.length == 0) **return** ;  
3.        
4.      Stack<Character> stack = **new** Stack<Character>();  
5.      **for**(**int** i = 1; i <= chs.length; i++)\{  
6.          combine(chs, 0, i, stack);  
7.      \}  
8.  \}  
9.  //从字符数组中第begin个字符开始挑选number个字符加入list中  
10. **public** **static** **void** combine(**char** \[\]chs, **int** begin, **int** number, Stack<Character> stack)\{  
11.        **if**(number == 0)\{  
12.         System.out.println(stack.toString());  
13.         **return** ;  
14.        \}  
15.        **if**(begin == chs.length)\{  
16.         **return**;  
17.        \}  
18.        stack.push(chs\[begin\]);  
19.        combine(chs, begin + 1, number - 1, stack);  
20.        stack.pop();  
21.        combine(chs, begin + 1, number, stack);  
22. \}

给一个字符串，比如ABC， 把所有的排列，即：ABC, ACB, BAC, BCA, CAB, CBC 都找出来。

解题思路：

对于一个n 位的字符串来讲，它是n-1位字符串的排列 加上 没有在 n -1 位字符串里 那个字符 的排列。 有点难理解，用例子说明：

对于字符串ABC来讲，它所有的排列就是 A + BC 的排列 加上 B + AC 的排列，再加上 C + AB的排列。

而BC的排列是 B + C 的排列 加上 C + B 的排列。

所以，对一个字符串，我们从中去一个值，然后求剩余部分的排列，然后把它们再组合在一起。所有，代码如下：

**\[java\]**  [view plain][]   [copy][view plain]

1.  // str has been sorted.  
2.      **public** **static** LinkedList<String> permutation(String str) \{  
3.            
4.          LinkedList<String> linkedString = **new** LinkedList<String>();   
5.          **if** (str.length() <= 1) \{  
6.              linkedString.add(str);  
7.              **return** linkedString;  
8.          \}   
9.          **for** (**int** i = 0; i < str.length() ; i++) \{  
10.             **char** ch = str.charAt(i);  
11.             //consider the case in which the characters may be duplicated.  
12.             **if** (i > 0 && ch == str.charAt(i - 1)) \{  
13.                 **continue**;  
14.             \}  
15.             String newStr = remove(str, i);  
16.             LinkedList<String> newStrList= permutation(newStr);   
17.             **for** (**int** j = 0; j < newStrList.size(); j++) \{  
18.                 linkedString.add(ch + newStrList.get(j));  
19.             \}  
20.         \}  
21.         **return** linkedString;  
22.     \}  
23.     //remove the ith character from the string  
24.     **public** **static** String remove(String str, **int** i) \{  
25.         **if** (i == 0) **return** str.substring(1, str.length());  
26.         **if** (i == str.length() - 1) **return** str.substring(0, i );  
27.         **return** str.substring(0, i) + str.substring(i + 1, str.length());  
28.     \}

这里贴出另一个permutation 的版本：

**\[java\]**  [view plain][]   [copy][view plain]

1.  **static** **void** swap(**char**\[\] arr, **int** idx1, **int** idx2) \{  
2.      **char** temp = arr\[idx1\];  
3.      arr\[idx1\] = arr\[idx2\];  
4.      arr\[idx2\] = temp;  
5.  \}  
6.    
7.  **static** **void** permutation(**char**\[\] arr, **int** index, **int** size) \{  
8.      **if** (index == size) \{  
9.          **for** (**int** i = 0; i < arr.length; i++) \{  
10.             System.out.print(arr\[i\] + " ");  
11.         \}  
12.         System.out.println();  
13.     \} **else** \{  
14.         **for** (**int** i = index; i < size; i++) \{  
15.             **if**(i != index && arr\[i\] == arr\[index\])  
16.                 **continue**;  
17.             swap(arr, i, index);  
18.             permutation(arr, index+1, size);  
19.             swap(arr, i, index);  
20.         \}  
21.     \}  
22. \}  
23.    \}

参考：[http://zhedahht.blog.163.com/blog/static/2541117420114172812217/][http_zhedahht.blog.163.com_blog_static_2541117420114172812217]

[http://shukuiyan.iteye.com/blog/1095637\#][http_shukuiyan.iteye.com_blog_1095637]

[view plain]: http://blog.csdn.net/beiyeqingteng/article/details/7051942#
[http_zhedahht.blog.163.com_blog_static_2541117420114172812217]: http://zhedahht.blog.163.com/blog/static/2541117420114172812217/
[http_shukuiyan.iteye.com_blog_1095637]: http://shukuiyan.iteye.com/blog/1095637#