Question

一道Java编程题，使用递归来做。

写一个叫做print的类函数，要求如下
public void print(String phrase)
In this method you should use recursive backtracking to find and print all anagrams that can be formed using all of the
letters of the given phrase, in the same order and format as in the example log on the previous page. For example, if your
anagram solver is using the dictionary corresponding to dict1.txt and you are passed the phrase "hairbrush", your
method should produce the following output:
[bar, huh, sir]
[bar, sir, huh]
[briar, hush]
[huh, bar, sir]
[huh, sir, bar]
[hush, briar]
[sir, bar, huh]
[sir, huh, bar]
You should throw an IllegalArgumentException if the string is null. An empty string generates no output.

别介意是全英文的。。具体要求请下载看PDF文档：http://www.cs.washington.edu/education/courses/cse143/12wi/homework/6/spec.pdf
谢谢！

Answer 1

import java.util.*; // in order to use the Set and Stack collections.
public class Anagrams {

private static String[] letters;

/**
* Anagrams, the constructor, initializes a new anagram solver over the given dictionary
* of words, and throws an IllegalArgumentException if the set passed is null.
* @param dictionary
*/
public Anagrams(Set<String> dictionary){
if(dictionary == null)
throw new IllegalArgumentException();
letters = dictionary.toArray(new String[0]);
}

/**
* getWords method returns a set containing all words from the dictionary that can be made
* using some or all of the letters in the given phrase, in alphabetical order, and throws
* an IllegalArgumentException if the set passed is null.
* @param phrase
* @return
*/
public Set<String> getWords(String phrase){
if(phrase == null)
throw new IllegalArgumentException();
Set<String> words = new TreeSet<String>();
LetterInventory phraseLetter = new LetterInventory(phrase);
for(String letter : letters){
if(phraseLetter.contains(letter)){
words.add(letter);
}
}
return words;
}

/**
* This first print method uses recursive backtracking to find and print all
* anagrams that can be formed using all of the letters of the given phrase,
* and throws an IllegalArgumentException if the set passed is null.
* @param phrase
*/
public void print(String phrase){
print(phrase, 0);
}

/**
* This second print method uses recursive backtracking to find and print all anagrams
* that can be formed using all of the letters of the given phrase and that include at
* most max words total, and throws an IllegalArgumentException if the set passed is null.
* @param phrase
* @param max
*/
public void print(String phrase, int max){
if(phrase == null || max < 0)
throw new IllegalArgumentException();
LetterInventory phraseLetter = new LetterInventory(phrase);
Stack<String> chosen = new Stack<String>();
String[] choices = getWords(phrase).toArray(new String[0]);
print(phraseLetter, chosen, choices, max);
}

/**
* This third print method is the basic recursive method of the two print methods above.
* @param phrase, the phrase that the user typed in.
* @param chosen, a collection of the words that are chosen to form the phrase using part
* of letters of the given phrase.
* @param choices, an String array that contains all the possible words that can be used
* to form the given phrase.
* @param max
*/
private static void print(LetterInventory phrase, Stack<String> chosen,String[] choices,int max){
if(phrase.isEmpty()){ //base case
System.out.println(chosen);
}else{ // recursive case
for(int i = 0; i<choices.length;i++){
if(phrase.contains(choices[i]) && (chosen.size() < max || max == 0)){
phrase.subtract(chosen.push(choices[i]));// choose
print(phrase, chosen, choices, max);// explore
phrase.add(chosen.pop());// backtrack.
}
}
}
}
}

Answer 2

public static int triangle(int n) {
if (n == 1) {
return 1;
} else {
return (n + triangle(n - 1));
}
}

程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

Answer 3

3个字符串进行全排列，用递归算法。下午要考试，不然可以写一写。下面是一个字符串全排列递归算法。你可以看一下。晚上回来写。

public class test{
static int count=0;
public static void main(String[] arg) throws ClassNotFoundException {
String s="1234";
long start=System.currentTimeMillis();
Pailie(s, " ");
System.out.println( "Total: "+count);
long end=System.currentTimeMillis();
System.out.println(end-start);
}
static void Pailie(String s,String p) {
if(s.length() <1) {
count++;
System.out.ptintln(p);
}
else {
int index[]=new int[s.length()];
for(int i=0;i<s.length();i++)
index[i]=s.indexOf(s.charAt(i));
for(int i=0; i <s.length(); i++) {
if(i==index[i])
Pailie(s.substring(1),p+s.substring(0,1));
s=s.substring(1)+s.substring(0,1);
}
}
}
}

Answer 4

如下

----------------------------------------------------------------------------------------
import java.util.ArrayList;
import java.util.List;

public class demo {

public static void main(String[] args) {
String[] array = { "bar", "huh", "sir" };
List<String> list = new ArrayList();
execute(array, list);
}

public static void execute(String[] array, List<String> list) {
for (int i = 0; i < array.length; i++) {
if (list.contains(array[i])) {
continue;
}
list.add(array[i]);
if (list.size() == array.length) {
String str = "";
for (int n = 0; n < list.size(); n++) {
str += list.get(n) + "\t";
}
System.out.println(str);
} else {
execute(array, list);
}
list.remove(list.size() - 1);
}
}
}

Answer 5

阶乘用递归实现！！