最近在研究一个问题，自己尝试些写了一个算法：
问题描述：给出一段字符，比如[a,b,c,d……]，输出任意长度大于n的字符组合
package com.txq.letter.combine;
import java.lang.ref.SoftReference;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.ConcurrentLinkedDeque;
/**
* 输出长度>len的字符串的任意组合，比如String s = "abc"，输出为"ab","ba","ac","ca"……字符的排列
*
* @author TongXueQiang
* @date 2016/03/01
* @since JDK 1.7
*/
public class LetterCombation {
// 存放字符的原始队列
private static Queue<Character> queue = new ConcurrentLinkedDeque<Character>();
// 组合过程中产生的第一个结果集
private static Queue<List<String>> firstResult = new ConcurrentLinkedDeque<List<String>>();
// 最终结果集
private static Set<String> finalResult = new HashSet<String>();
// 组合的层级数，从2开始
private static int level = 2;
/**
* 任意字母组合
*
* @param word
* @param len
* @return
*/
public Set<String> outputLetterCombina(String word, int len) {
if (word == null || word.equals("")) {
return null;
}
// 1.把word加入到原始队列中
init(word);
// 2.产生第一次结果集
firstResult = outputFirstCombination();
// 3.循环进行下一层级的组合，并得到最终结果集
finalResult = outputCombination(firstResult, level, word);
// 4.去除不符合期望的字符组合
return removeUnexpectedLetterComb(finalResult, len);
}
/**
* 去除不符合期望的字符串
* @param finalResult2
* @return
*/
private Set<String> removeUnexpectedLetterComb(Set<String> result, int len) {
List<String> deleteList = new ArrayList<String>();
for (String s : result) {
if (s.length() <= len) {
deleteList.add(s);
}
}
result.removeAll(deleteList);
return result;
}
/**
* 产生原始队列
*
* @param word
*/
public Queue<Character> init(String word) {
if (word == null || word.equals("")) {
return null;
}
for (int i = 0;i < word.length();i++) {
Character c = Character.valueOf(word.charAt(i));
if (c.equals(‘ ‘) || c.equals(‘\n‘) || c.equals(‘\t‘) || c.equals(‘\r‘)) {
continue;
}
queue.add(c);
}
return queue;
}
/**
* 倒置字符串
*
* @param word
* @return
*/
public String reverse(String word) {
StringBuffer result = new StringBuffer();
for (int i = word.length() - 1; i >= 0; i--) {
result.append(word.charAt(i));
}
return result.toString();
}
/**
* 倒置字符串，比如abc,倒置后为cab，abcd,倒置后为dabc……
*
* @param word
* @return
*/
public String reverseCombination(String word) {
char s[] = word.toCharArray();
List<String> ss = new ArrayList<String>();
StringBuffer sb = new StringBuffer();
SoftReference<StringBuffer> srf = new SoftReference<StringBuffer>(sb);
for (int i = 0; i < s.length - 1; i++) {
sb.append(s[i]);
}
// 把除最后一个字符意外的全部字符串加载到list中
ss.add(sb.toString());
sb = null;
sb = new StringBuffer();
sb.append(s[s.length - 1]);
// 把最后一个字符加载到list中
ss.add(sb.toString());
Collections.reverse(ss);// 倒置处理
sb = null;
sb = new StringBuffer();
for (String s0 : ss) {
sb.append(s0);
}
// 输出最后结果
return sb.toString();
}
/**
* 输出长度为2的字母组合，作为第一个结果集,以备后续的组合使用
* @return
*/
public Queue<List<String>> outputFirstCombination() {
StringBuffer sb = null;
List<String> cell = null;
SoftReference<List<String>> srf = new SoftReference<List<String>>(cell);
SoftReference<StringBuffer> srf0 = new SoftReference<StringBuffer>(sb);
// 1.依次取出第一个字符，与剩下的字符组合
char ch = queue.poll();
for (char cha : queue) {
cell = new ArrayList<String>();
sb = new StringBuffer();
sb.append(ch).append(cha);
// 加入到cell中
cell.add(sb.toString());
cell.add(reverse(sb.toString()));
// 把cell加入到首个结果集中
firstResult.add(cell);
sb = null;
cell = null;
}
// 递归终止条件
if (queue.size() != 1) {
outputFirstCombination();
}
return firstResult;
}
/**
* 输出组合，循环对输入的结果集中的每个cell处理，产生新的cell，然后把新的cell加载到中间结果集中，最后返回最后结果
*
* @param handleResult
* @param level
* @return
*/
public Set<String> outputCombination(Queue<List<String>> inputResult, int level, String word) {
// 定义新的中间结果集
Queue<List<String>> middleResult = new ConcurrentLinkedDeque<List<String>>();
SoftReference<Queue<List<String>>> srf = new SoftReference<Queue<List<String>>>(middleResult);
StringBuffer sb = null;
// 1.把handleResult加入到最终结果集中
finalResult = addToFinalResult(inputResult);
// 2.清空队列
queue.clear();
// 3.对输入的结果集进行处理，进行下一层级的组合
List<String> cell = inputResult.poll();
while (cell != null) {
// 新的cell
List<String> newCell = null;
// ①.初始化队列
queue = init(word);
// ②.从cell中取出第一个字符串，然后去除原始队列中与之匹配的字符串
removeStrFromOriginalQueue(cell);
// ③.cell与原始队列中剩下的字符串进行组合,产生新的cell
originalQueueToCellCombination(newCell, cell, middleResult, sb);
// ④.清空队列
queue.clear();
// ⑤.下一个单元
cell = inputResult.poll();
}
inputResult = null;
++ level;// 4.层级叠加
// 5.递归终止条件
if (level != word.length()) {
outputCombination(middleResult, level, word);
}
// 6.处理最后的中间结果集
addToFinalResult(middleResult);
middleResult = null;
return finalResult;
}
/**
* cell与原始队列中剩下的字符串进行组合,产生新的cell
*
* @param newCell
* @param cell
* @param middleResult
* @param sb
*/
private void originalQueueToCellCombination(List<String> newCell, List<String> cell,
Queue<List<String>> middleResult, StringBuffer sb) {
SoftReference<List<String>> srf = new SoftReference<List<String>>(newCell);
SoftReference<StringBuffer> srf0 = new SoftReference<StringBuffer>(sb);
for (char c : queue) {
newCell = new ArrayList<String>();
for (String s : cell) {
sb = new StringBuffer();
sb.append(s).append(c);
newCell.add(sb.toString());
newCell.add(reverseCombination(sb.toString()));
sb = null;// 不用的对象
}
// 把newCell加载到中间结果集中
middleResult.add(newCell);
newCell = null;
}
}
/**
* 从cell中取出第一个字符串，在原始队列中移除与之匹配的字符串
*
* @param cell
*/
private void removeStrFromOriginalQueue(List<String> cell) {
String firstWord = cell.get(0);
for (int i = 0; i < firstWord.length(); i++) {
queue.remove(firstWord.charAt(i));
}
}
/**
* 输出到最终结果集中
*
* @param middleResult
*/
public Set<String> addToFinalResult(Queue<List<String>> middleResult) {
for (List<String> cell : middleResult) {
finalResult.addAll(cell);
}
return finalResult;
}
}
原文：http://www.cnblogs.com/txq157/p/5239936.html