Gosper's Hack 算法

XIN 队算法之枚举组合 .

枚举组合的一个非递归做法叫 Gosper's Hack 算法，思路就是对每个组合，用 01 串表示其选或不选，这样必然可以表示所有组合 .

我们考虑如何生成一个组合的下一个组合，因为是组合，所以我们要保证串串的 popcount 不变，这样就考虑把最后一个 01 变成 10，这样显然是对的 .

而且要保证生成完的串串 \(b'\) 和原来的串串 \(b\) 的差值 \(b'-b\) 最小，这样我们才能保证生成所有组合，于是我们只需要把所有 1 集中到最右边即可 .

我们考虑如何用位运算描述这个过程，具体可以看下面的代码手玩一下 .

比如按字典序生成 \(n\) 元集合所有 \(k\) 元子集就可以写为

const int N = 1 << 25;
int n, k, state[N], cc;
int main()
{
	scanf("%d%d", &n, &k);
	if (!k) return 0;
	int cur = (1 << k) - 1, limit = (1 << n);
	while (cur < limit)
	{
		state[++cc] = cur;
		int lb = cur & -cur, r = cur + lb;
		cur = ((r ^ cur) >> __builtin_ctz(lb) + 2) | r;
		// 如果不用 builtin 函数可以写 cur = (((r ^ cur) >> 2) / lb) | r; 
	}
	for (int i=cc; i>=1; i--, puts(""))
		for (int j=n-1; j>=0; j--)
			if (state[i] >> j & 1) printf("%d ", n-j); 
	return 0;
}

时间复杂度为 \(\displaystyle O\left(\dbinom nk\cdot n\right)\)，非常的高效，也非常的简洁 .