GL~19′Life. 今天总是好过昨天~

package com.ll19.test;
 
import java.util.ArrayList;
import java.util.Calendar;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
 
public class PetFish {
 
	/**
	 * 在一条街上，有5座房子，喷了5种颜色,每个房里住着不同国籍的人,每个人喝不同的饮料，抽不同品牌的香烟，养不同的宠物。问题：谁养鱼?
	 * 
	 * 提示：
	 * 
	 * 1、英国人住红色房子 2、瑞典人养狗 3、丹麦人喝茶 4、绿色房子在白色房子左面 5、绿色房子主人喝咖啡 6、抽Pall Mall 香烟的人养鸟
	 * 7、黄色房子主人抽Dunhill 香烟 8、住在中间房子的人喝牛奶 9、 挪威人住第一间房 10、抽Blends香烟的人住在养猫的人隔壁
	 * 11、养马的人住抽Dunhill 香烟的人隔壁 12、抽Blue Master的人喝啤酒 13、德国人抽Prince香烟
	 * 14、挪威人住蓝色房子隔壁 15、抽Blends香烟的人有一个喝水的邻居
	 * 
	 * @author <a href="http://www.LL19.com/">LL19.com</a>
	 * 
	 */
 
	// 保存所有房子的组合
	private static ArrayList<string> houseList = new ArrayList</string><string>();
 
	// 保存所有宠物的组合
	private static ArrayList</string><string> petList = new ArrayList</string><string>();
 
	// 保存所有烟的组合
	private static ArrayList</string><string> smokeList = new ArrayList</string><string>();
 
	// 保存所有饮料的组合
	private static ArrayList</string><string> drinkList = new ArrayList</string><string>();
 
	// 保存所有国籍的组合
	private static ArrayList</string><string> peopleList = new ArrayList</string><string>();
 
	// 过滤用
	private static ArrayList</string><string> filterList;
 
	public static void main(String[] args) {
 
		// 开始时间
		long l1 = Calendar.getInstance().getTimeInMillis();
 
		// 房子 "绿色", "红色", "蓝色", "黄色", "白色"
		ArrayList</string><string> houseArray = new ArrayList</string><string>();
		houseArray.add("绿色");
		houseArray.add("红色");
		houseArray.add("蓝色");
		houseArray.add("黄色");
		houseArray.add("白色");
		String[] house = new String[5];
 
		rotate(house, houseArray, houseArray.size(), houseList);
 
		// 宠物 "猫", "狗", "鱼", "马", "鸟"
		ArrayList</string><string> petArray = new ArrayList</string><string>();
		petArray.add("猫");
		petArray.add("狗");
		petArray.add("鱼");
		petArray.add("马");
		petArray.add("鸟");
		String[] pet = new String[5];
 
		rotate(pet, petArray, petArray.size(), petList);
 
		// 烟 "PallMall", "Dunhill", "Blends", "BlueMaster", "Prince"
		ArrayList</string><string> smokeArray = new ArrayList</string><string>();
		smokeArray.add("PallMall");
		smokeArray.add("Dunhill");
		smokeArray.add("Blends");
		smokeArray.add("BlueMaster");
		smokeArray.add("Prince");
		String[] smoke = new String[5];
 
		rotate(smoke, smokeArray, smokeArray.size(), smokeList);
 
		// 饮料 "茶", "牛奶", "水", "咖啡", "啤酒"
		ArrayList</string><string> drinkArray = new ArrayList</string><string>();
		drinkArray.add("茶");
		drinkArray.add("牛奶");
		drinkArray.add("水");
		drinkArray.add("咖啡");
		drinkArray.add("啤酒");
		String[] drink = new String[5];
 
		rotate(drink, drinkArray, drinkArray.size(), drinkList);
 
		// 国籍 "英国人", "瑞典人", "丹麦人", "德国人", "挪威人"
		ArrayList</string><string> peopleArray = new ArrayList</string><string>();
		peopleArray.add("英国人");
		peopleArray.add("瑞典人");
		peopleArray.add("丹麦人");
		peopleArray.add("德国人");
		peopleArray.add("挪威人");
		String[] people = new String[5];
 
		rotate(people, peopleArray, peopleArray.size(), peopleList);
 
		// 队列本身可以过滤的
		// 住在中间房子的人喝牛奶
		filterList = new ArrayList</string><string>();
		for (int drinkNo = 0; drinkNo < drinkList.size(); drinkNo++) {
			String[] tmp = filter(drinkList, drinkNo);
			if (tmp[2].equals("牛奶")) {
				filterList.add(drinkList.get(drinkNo));
			}
		}
		drinkList = filterList;
 
		// 挪威人住第一间房
		filterList = new ArrayList<String>();
		for (int peopleNo = 0; peopleNo < peopleList.size(); peopleNo++) {
			String[] tmp = filter(peopleList, peopleNo);
			if (tmp[0].equals("挪威人")) {
				filterList.add(peopleList.get(peopleNo));
			}
		}
		peopleList = filterList;
 
		// 绿色房子在白色房子左面
		filterList = new ArrayList<String>();
		for (int houseNo = 0; houseNo < houseList.size(); houseNo++) {
			String[] tmp = filter(houseList, houseNo);
			for (int tmpNo = 0; tmpNo < tmp.length; tmpNo++) {
				// 英国人住红色房子 因为挪威人住第一间房 所以第一间不是红色 挪威人住蓝色房子隔壁 所以蓝色是第二间房
				// 绿色房子主人喝咖啡 住在中间房子的人喝牛奶 所以绿色房子不在中间
				if (!tmp[0].equals("红色") && tmp[1].equals("蓝色")
						&& !tmp[2].equals("绿色")) {
					if (tmp[tmpNo].equals("绿色")) {
						// 绿色不是最后一间
						if (tmpNo != 4 && tmp[tmpNo + 1].equals("白色")) {
							filterList.add(houseList.get(houseNo));
						}
					}
				}
			}
		}
		houseList = filterList;
 
		// 开始过滤其他条件
		boolean end = false;
 
		while (!end) {
 
			// 英国人住红色房子
			peopleList = filterOneToOne(peopleList, "英国人", houseList, "红色");
			houseList = filterOneToOne(houseList, "红色", peopleList, "英国人");
			// 绿色房子主人喝咖啡
			houseList = filterOneToOne(houseList, "绿色", drinkList, "咖啡");
			drinkList = filterOneToOne(drinkList, "咖啡", houseList, "绿色");
			// 瑞典人养狗
			peopleList = filterOneToOne(peopleList, "瑞典人", petList, "狗");
			petList = filterOneToOne(petList, "狗", peopleList, "瑞典人");
			// 丹麦人喝茶
			peopleList = filterOneToOne(peopleList, "丹麦人", drinkList, "茶");
			drinkList = filterOneToOne(drinkList, "茶", peopleList, "丹麦人");
			// 抽Pall Mall 香烟的人养鸟
			smokeList = filterOneToOne(smokeList, "PallMall", petList, "鸟");
			petList = filterOneToOne(petList, "鸟", smokeList, "PallMall");
			// 黄色房子主人抽Dunhill
			houseList = filterOneToOne(houseList, "黄色", smokeList, "Dunhill");
			smokeList = filterOneToOne(smokeList, "Dunhill", houseList, "黄色");
			// 德国人抽Prince香烟
			peopleList = filterOneToOne(peopleList, "德国人", smokeList, "Prince");
			smokeList = filterOneToOne(smokeList, "Prince", peopleList, "德国人");
			// 抽Blue Master的人喝啤酒
			smokeList = filterOneToOne(smokeList, "BlueMaster", drinkList, "啤酒");
			drinkList = filterOneToOne(drinkList, "啤酒", smokeList, "BlueMaster");
			// 抽Blends香烟的人住在养猫的人隔壁
			petList = filterOneToTwo(smokeList, "Blends", petList, "猫");
			smokeList = filterOneToTwo(petList, "猫", smokeList, "Blends");
			// 养马的人住抽Dunhill 香烟的人隔壁
			smokeList = filterOneToTwo(petList, "马", smokeList, "Dunhill");
			petList = filterOneToTwo(smokeList, "Dunhill", petList, "马");
			// 抽Blends香烟的人有一个喝水的邻居
			drinkList = filterOneToTwo(smokeList, "Blends", drinkList, "水");
			smokeList = filterOneToTwo(drinkList, "水", smokeList, "Blends");
 
			if (houseList.size() == 1 && petList.size() == 1
					&& smokeList.size() == 1 && drinkList.size() == 1
					&& peopleList.size() == 1) {
				end = true;
			}
 
		}
 
		System.out.println(houseList);
		System.out.println(petList);
		System.out.println(smokeList);
		System.out.println(drinkList);
		System.out.println(peopleList);
 
		// 结束时间
		long l2 = Calendar.getInstance().getTimeInMillis();
		System.out.println("用时（毫秒）: " + (l2 - l1));
	}
 
	// 递规方法 算出每个种类的组合
	public static void rotate(String[] result, List<String> al, int index,
			ArrayList</string><string> list) {
		index = result.length - index;
		if (index == result.length - 1) {
			result[index] = (String) al.get(0);
			organizeNum(result, list);
		}
		for (int s1 = 0; s1 < al.size(); s1++) {
			result[index] = (String) al.get(s1);
			ArrayList<String> al1 = new ArrayList</string><string>(al);
			al1.remove(result[index]);
			rotate(result, al1, al1.size(), list);
		}
	}
 
	// 加入容器
	public static void organizeNum(String[] result, ArrayList</string><string> list) {
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < result.length; i++) {
			sb.append(result[i].toString() + ";");
		}
		String pstr = sb.toString();
		list.add(pstr);
	}
 
	// 过滤器
	public static String[] filter(ArrayList<String> list, int n) {
		String tmp = list.get(n);
		String[] tmp2 = new String[5];
		tmp2 = tmp.split(";");
		return tmp2;
	}
 
	// 过滤类似“英国人住红色房子”这样的条件
	public static ArrayList</string><string> filterOneToOne(ArrayList</string><string> List1,
			String text1, ArrayList</string><string> List2, String text2) {
		Set<object> set = new HashSet</object><object>();
		filterList = new ArrayList<string>();
		for (int no = 0; no < List2.size(); no++) {
			String[] tmp = filter(List2, no);
			for (int no1 = 0; no1 < tmp.length; no1++) {
				if (tmp[no1].equals(text2)) {
					if (!set.contains(no1)) {
						set.add(no1);
						for (int no2 = 0; no2 < List1.size(); no2++) {
							String[] tmp2 = filter(List1, no2);
							if (tmp2[no1].equals(text1)) {
								filterList.add(List1.get(no2));
							}
						}
					}
				}
			}
		}
		return filterList;
 
	}
 
	// 过滤类似“抽Blends香烟的人住在养猫的人隔壁”这样的条件
	public static ArrayList<String> filterOneToTwo(ArrayList</string><string> List1,
			String text1, ArrayList</string><string> List2, String text2) {
 
		Set<object> set = new HashSet</object><object>();
		Set</object><object> set2 = new HashSet</object><object>();
		filterList = new ArrayList<string>();
 
		for (int no = 0; no < List1.size(); no++) {
			String[] tmp = filter(List1, no);
			for (int tmpNo = 0; tmpNo < tmp.length; tmpNo++) {
				if (tmp[tmpNo].equals(text1)) {
					if (!set.contains(tmpNo)) {
						set.add(tmpNo);
						int tmpNo2;
						if (tmpNo == 0) {
							tmpNo2 = 1;
							if (!set2.contains(tmpNo2)) {
								set2.add(tmpNo2);
								for (int no2 = 0; no2 < List2.size(); no2++) {
									String[] tmp2 = filter(List2, no2);
									if (tmp2[tmpNo2].equals(text2)) {
										filterList.add(List2.get(no2));
									}
								}
							}
						} else if (tmpNo == 4) {
							tmpNo2 = 3;
							if (!set2.contains(tmpNo2)) {
								set2.add(tmpNo2);
								for (int no2 = 0; no2 < List2.size(); no2++) {
									String[] tmp2 = filter(List2, no2);
									if (tmp2[tmpNo2].equals(text2)) {
										filterList.add(List2.get(no2));
									}
								}
							}
						} else {
							tmpNo2 = tmpNo + 1;
							if (!set2.contains(tmpNo2)) {
								set2.add(tmpNo2);
								for (int no2 = 0; no2 < List2.size(); no2++) {
									String[] tmp2 = filter(List2, no2);
									if (tmp2[tmpNo2].equals(text2)) {
										filterList.add(List2.get(no2));
									}
								}
							}
							tmpNo2 = tmpNo - 1;
							if (!set2.contains(tmpNo2)) {
								set2.add(tmpNo2);
								for (int no2 = 0; no2 < List2.size(); no2++) {
									String[] tmp2 = filter(List2, no2);
									if (tmp2[tmpNo2].equals(text2)) {
										filterList.add(List2.get(no2));
									}
								}
							}
						}
					}
				}
			}
		}
		return filterList;
 
	}
 
}