小程序：递归实现所有变位词的排列组合

本文主要是介绍小程序：递归实现所有变位词的排列组合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

找出一个单词的所有变位词，例如给到单词“stop”，找到对应的变位词“pots”和“tops”。

采用暴力解法的话，把所有的可能性都排列组合一遍，一个一个判断；在排列组合这步很适合用递归来实现，写了个小程序测试了下。

输入样例：abcd

输出样例：abcd,abdc,acbd,acdb,adbc,adcb,bacd,badc,bcad,bcda,bdac,bdca,cabd,cadb,cbad,cbda,cdab,cdba,dabc,dacb,dbac,dbca,dcab,dcba

递归部分的实现：

/*** 递归的核心部分，将结果保存到anagrams_arr中* @param prefix 变位词中的前半部分，保持不变* @param ana 需要递归遍历的内容*/
private void anagrams(String prefix,String ana)
{if(ana.length() == 1)anagrams_arr.add(prefix + ana);for(int i = 0; i<ana.length();i++){//新的前缀是：原有前缀+此次选定的字母；递归的内容减去此次选定的字母anagrams(prefix + ana.charAt(i),ana.substring(0,i) + ana.substring(i+1));}
}


e.g. 传入的数据是“123”
第一层anagrams参数（“”，“123”）；
由于输出的参数长度不是1，利用循环重新调用递归代码；
第二层anagrams参数round1（“1”，“23”）
输入的参数长度仍然不为1，利用循环重新调anagrams；
第三层anagrams参数round1（“12”，“3”）
输入参数长度是1，将“123”保存，退出第三层循环round1回到第二层anagrams，利用循环调第三层anagrams；
第三层anagrams参数round2（“13”，“2”）
……



完整代码如下所示，供参考：
public class Anagram {private String word;private ArrayList<String> anagrams_arr = new ArrayList<String>();private String[] anagrams;public static void main(String args[]){Anagram test = new Anagram();String abc = "abcd";String[] result = test.getAnagrams(abc);for(int i = 0; i<result.length; i++)System.out.print(result[i] + ",");}public String[] getAnagrams(String word){anagrams_arr.clear();anagrams("",word);anagrams = new String[anagrams_arr.size()];anagrams_arr.toArray(anagrams);return anagrams;}/*** 递归的核心部分，将结果保存到anagrams_arr中* @param prefix 变位词中的前半部分，保持不变* @param ana 需要递归遍历的内容*/private void anagrams(String prefix,String ana){if(ana.length() == 1)anagrams_arr.add(prefix + ana);for(int i = 0; i<ana.length();i++){//新的前缀是：原有前缀+此次选定的字母；递归的内容减去此次选定的字母anagrams(prefix + ana.charAt(i),ana.substring(0,i) + ana.substring(i+1));}}
}