[Leetcode] 1238. Circular Permutation in Binary Representation

https://leetcode.com/problems/circular-permutation-in-binary-representation/
入力:整数n,start
出力:startで始まる0から2^n-1の数値リスト(nとn+1をバイナリで表す場合は1ビットのみ、startと最後の値をバイナリで表す場合は1ビットのみ).
整数aを2進数として表す場合、aと1ビットの数だけ差をつける方法は整数a를 2^n과 XOR 연산을 수행である.aが5である場合、5のバイナリ表現は101である.101に対して1,2,4とXOR演算を行います.5(101) ^ 1(001) = 4(100) 5(101) ^ 2(010) = 7(111) 5(101) ^ 4(100) = 1(001)結果として得られた2進数はいずれも5と比較して1ビットのみ異なる.対応する解答でアルゴリズムを書くことができます.
また,アルゴリズムを記述する際には,整数a와 b가 2진수 표현에서 1개의 비트만 다른지 확인が必要となる場合がある.この場合、次のように処理されます.整数aおよびbは5および7であると仮定する.
1)まずaとbに対してXOR演算を行い,変数xに格納する.

int x = (5^7); // x=2 (101^111=010)

2)xに対してx-1とAND演算を行う.結果が0の場合、2つの数字は2進数で比較され、1ビットだけ異なる.

int result = (x&(x-1)); // result=0 (010^001=000)

コード#コード#

class Solution {
    public List<Integer> circularPermutation(int n, int start) {
		List<Integer> res = new ArrayList<>();
		Set<Integer> set = new HashSet<>();
		res.add(start);
		set.add(start);
		dfs(n, set, res, start);
        
        return res;
    }
    
	static boolean dfs(int n, Set<Integer> set, List<Integer> res, int start) {
		if (set.size() == (int) Math.pow(2, n)) {
			int x = res.get(res.size() - 1) ^ start;
			return (x & (x - 1)) == 0;
		}
		int last = res.get(res.size() - 1);
		for (int i = 0; i < n; i++) {
			int next = (last ^ (1 << i));
			if (!set.contains(next)) {
				set.add(next);
				res.add(next);
				if (dfs(n, set, res, start)) {
					return true;
				}
				set.remove(next);
				res.remove(res.size() - 1);
			}
		}
		return false;
	}
}

コードは次のコメントを参照しています.
https://leetcode.com/problems/circular-permutation-in-binary-representation/discuss/414145/Java-DFS-%2B-Bit
別の解説を見て、Greyコードを使えば4行でコードを作ることができることを知りました
上のアルゴリズムを作るのにも長い時間がかかり、4行の説明を見て、思わず失笑した.🤣

(私と反応の差が少ない人がいました…ははは)Grey Code는 이진법 부호의 일종으로, 연속된 수가 1개의 비트만 다른 특징을 지닌다. 연산에는 쓰이진 않고 주로 데이터 전송, 입출력 장치, 아날로그-디지털 간 변환과 주변장치에 쓰인다. -위키백과Grey Codeに関する追加の説明のリンクを添付します.
https://cp-algorithms.com/algebra/gray-code.html
https://woodforest.tistory.com/147
Grey Codeを用いてコードを記述することで、以下に示すような単純なコードを記述することができる.
コード#コード#

    public List<Integer> circularPermutation(int n, int start) {
       List<Integer> res = new ArrayList<>();
       for (int i = 0; i < 1 << n; ++i)
           res.add(start ^ i ^ i >> 1);
       return res;
   }

コードは次のコメントを参照しています.
https://leetcode.com/problems/circular-permutation-in-binary-representation/discuss/414203/JavaC%2B%2BPython-4-line-Gray-Code