C++でのバイナリ表現の循環順列

2つの整数nがあり、開始するとします。私たちのタスクは、次のように（0,1,2 .....、2 ^ n -1）の順列pを返すことです-

• p[0]=開始
• p[i]とp[i+ 1]は、バイナリ表現が1ビットだけ異なります。
• p[0]とp[2^ n -1]も、バイナリ表現で1ビットだけ異なる必要があります。

したがって、入力がn=2およびstart=3の場合、返される配列は[3,2,0,1]になり、これらは[11,10,00,01]

これを解決するには、次の手順に従います-

• ansは配列です
• 0〜2^nの範囲のiの場合
  • start XOR i XOR i/2をansに挿入します
• 回答を返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
         cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> circularPermutation(int n, int start) {
      vector <int> ans;
      for(int i = 0 ; i < 1<<n; i++){
         ans.push_back(start ^ i ^(i>>1));
      }
      return ans;
   }
};
main(){
   Solution ob;
   print_vector(ob.circularPermutation(5,3));
}

入力

5
3

出力

[3, 2, 0, 1, 5, 4, 6, 7, 15, 14, 12, 13, 9, 8, 10, 11, 27, 26, 24, 25, 29, 28, 
30, 31, 23, 22, 20, 21, 17, 16, 18, 19, ]