线性代数

考虑这个排列是怎样生成的。转述一下题意，可以发现，$\operatorname{popcount}(P_i \oplus P_{i+1 \mod {2^n}})=K$，也即全集$\text{msk}=2^N-1$的一个大小为$K$的子集。

由于这是一个环排列，我们不妨令$P_0=0$。这样一来，$P_i=\operatorname{\bigoplus}\limits_{j=1}^{i}S_j, |S_j|=K$。结合上文可知，这是一个相邻元素二进制位恰相差$K$位的格雷码问题。有$K=1$时，满足条件的$S_j$恰有$N$个，也就是$N$位格雷码。

考虑推广。我们发现，如果按照类格雷码的方式生成排列，则所有的$S_j$应构成异或空间，其大小应当恰为$2^N$，并且由线性空间知识可以得到，该线性空间的秩（基的大小）应当恰为$N$。这恰好符合$N$位格雷码的构造。因此，只要满足上述条件，就一定能够生成符合题意的排列。

可以证明，除了$2\mid K \lor (K=N \land N>1)$以外，总是有满足条件的线性空间生成的。

下述解法的时间复杂度$\operatorname{O}\left(\dbinom{N}{K}+2^N\right)$。 （更多…）