格雷碼(Gray Code)應用

Main.java

public class Main {
	/*
	 * 題目 任意給四個位置分別是1或0或2(比如1221或2012), 
	 * 假如位置是2那就要再給一個1跟0, 
	 * 比如1002就要變成1001跟1000
	 * 2002就要變成1000,1001,0000,0001
	 */

	/*
	 * 作法 Step.1 先找出格雷碼找出所有解 Step.2 將輸入的資料以遮罩方式與Step.1找出的鎖有解進行比對
	 * 
	 * 格雷碼參考:https://openhome.cc/Gossip/AlgorithmGossip/GrayCode.htm
	 */
	public static void main(String[] args) {
		print("1");
		print("10");
		print("02");
		print("021");
		print("1001");
		print("1001");
		print("1002");
		print("2002");
		print("2022");
		print("2222");
	}

	public static String[] print(String input) {
		String[] grayCodeArr = genGrayCode(input.length());// 先產生格雷碼

		System.out.println("input:" + input);
		System.out.print("output:");

		int count = 0;// 檢查有幾個2
		String[] inputArr = input.split("");
		for (int i = 0; i < inputArr.length; i++) {
			if (inputArr[i].equals("2")) {
				count = count + 1;
			}
		}
		int sum = 1;// 計算總共有幾個解;
		for (int i = 0; i < count; i++) {
			sum = sum * 2;
		}
		System.out.println("總共有:" + sum + "個解");

		System.out.print("output:");
		String[] output = new String[sum];
		int i = -1;
		for (String grayCode : grayCodeArr) {
			if (check(input, grayCode)) {
				i = i + 1;
				output[i] = grayCode;
				System.out.print(grayCode + ", ");
			}
		}

		System.out.println("\n");

		return output;
	}

	private static boolean check(String input, String grayCode) {
		String[] inputArr = input.split("");
		String[] grayCodeArr = grayCode.split("");

		for (int i = 0; i < inputArr.length; i++) {
			if (inputArr[i].equals("2")) {
				continue;
			}
			if (!inputArr[i].equals(grayCodeArr[i])) {
				return false;
			}
		}

		return true;
	}

	public static String[] genGrayCode(int n) {
		String[] graycode = new String[(int) Math.pow(2, n)];

		if (n == 1) {
			graycode[0] = "0";
			graycode[1] = "1";
			return graycode;
		}

		String[] last = genGrayCode(n - 1);

		for (int i = 0; i < last.length; i++) {
			graycode[i] = "0" + last[i];
			graycode[graycode.length - 1 - i] = "1" + last[i];
		}

		return graycode;
	}
}

輸出結果如下
input:1
output:總共有:1個解
output:1,

input:10
output:總共有:1個解
output:10,

input:02
output:總共有:2個解
output:00, 01,

input:021
output:總共有:2個解
output:001, 011,

input:1001
output:總共有:1個解
output:1001,

input:1001
output:總共有:1個解
output:1001,

input:1002
output:總共有:2個解
output:1001, 1000,

input:2002
output:總共有:4個解
output:0000, 0001, 1001, 1000,

input:2022
output:總共有:8個解
output:0000, 0001, 0011, 0010, 1010, 1011, 1001, 1000,

input:2222
output:總共有:16個解
output:0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000,