next_permutation 的实现

CPP

bool nxtp(){
	int i=n-1;
	for(;i>=1;i--)if(a[i]<a[i+1])break;
	if(!i)return 0;
	int j=n;
	for(;j>=1;j--)if(a[i]<a[j])break;
	std::swap(a[i],a[j]);
	std::reverse(a+1+i,a+1+n);
	return 1;
}

没什么多说的，就是上面这么做的。

next_permutaion 均摊复杂度证明

方法：得到每次最长下降后缀长度之和，除以

n!

就是答案。

打表找规律
递推
数学计算

打表找规律

使用 nxtp 函数打表，注意力惊人可得：

f_i=f_{i-1}\times i+1

递推

令当

n=i

的时候最长下降后缀长度之和为

f_i

。

f_1=1

f_i

第一位随便选，所有是

n

，然后

n-1

位与

f_{i-1}

相同，但最后会多一份贡献

n,n-1,n-2,\cdots,2,1

，前面没考虑到，所以加一。

f_i=f_{i-1}\times i+1

数学

\boxed{\text{横看成岭侧成峰}}

某些表格看横再看竖，能有不同发现。
从

n

个数里分别选

1

个，

2

个，

3

个，使得其后面

1,2,3

个数是递减的。

f_i=\sum\limits^{n}_{j=1} g_j

g_j=\frac{n!}{j!}

结论

三种方法可得

f_i=\sum\limits^{n}_{j=1}\frac{n!}{j!}

。
所有均摊复杂度是

\frac{f_i}{ n!} \lt e-1

因此均摊时间复杂度为

O(1)

。

Gosper's hack

给你一个二进制数

x

，请算出第一个比

x

大且

1

的数量与

x

相同的数。
不难想到，做一遍 next_permutaion 即可。
但 Gosper 想出了仅用算数就做出来的方法

O(1)

。

Gosper's hack 解法

引用 Deepseek 的解释。

推导公式

现在，让我们尝试从原理上推导出这个公式。我们需要从一个有k个1的二进制数x，生成下一个有k个1的二进制数。

Gosper's Hack 算法详解

1. 找到最右边的可移动 1

设当前数为

x

，其二进制表示为：

x = \cdots 011\cdots 1\underline{1}00\cdots

其中：

下划线标记的是最右边连续 1 块的最左侧 1
该位置的值可通过低位运算得到：

\text{lowbit} = x \& (\sim x + 1) = x \& (-x)

2. 移动该 1 位

将该 1 向左移动一位：

y = x + \text{lowbit}

效果示例：

00111 \xrightarrow{+00001} 01000

3. 处理右侧的 1

移动后需要补回因进位而丢失的 1：

计算异或： $x \oplus y = \cdots 1111000\cdots$
调整步骤： $\text{adjust} = (\frac{x \oplus y}{\text{lowbit}}) \gg 2$

先把高位用异或消掉，然后将

11111111

放到结尾，最后会多两个

1

，直接右移截断。
至于为何会多两个

1

，自己想。

4. 组合结果

最终的下一个数为：

\text{next} = y \mid \text{adjust}

步骤	数字
$x$	$00111$
$\text{lowbit}$	$00001$
$y = x + \text{lowbit}$	$01000$
$x \oplus y$	$01111$
$(x \oplus y) \gg 2$	$00011$
$\text{adjust}$	$00011$
$\text{next}$	$01011$

本课要点

\boxed{\text{关注一切问题}}

next_permutaion 与 Gosper's Hack

文章操作