46. Permutations

2020-05-18 本文已影响0人 xxxcoder

算法 1:

递归
数组 $a = \{a_1, a_2, …, a_n\}$ 的全排列，等价于 $\{a_2, a_3, …, a_n\}$ 全排列与 $a_1$ 可能的取值组合得到。

算法 2:

计算一个排列 $\{a_1, a_2, …, a_n\}$ 按字典升序排列的紧邻下一个排列
为了获取一个排列的下一个排列，应对其中一个子序列做调整，使原排列变大为紧邻的下一个排列。假设下一个排列为， $a_1', a_2', …, a_{m-1}', a_m', a_{m+1}', …, a_n'$ 。可知， $a_1 = a_1', a_2 = a_2', …, a_{m-1} = a_{m-1}'$ 即只应对子序列 $a_m, a_m+1,…, a_n$ 做调整，使其变为紧邻的下一个排列。
为使下一个排列与当前排列变化最小，则子序列 $a_m, a_{m+1},…, a_ n$ 应满足如下条件： $a_m, a_{m+1}, .., a_n$ 是所有以 $a_m$ 开头，元素为 $\{a_m, a_{m+1}, .., a_n\}$ 组成的排列中，最大的一个。则有如下约束： $a_m < a_{m+1} > a_{m+2} > … > a_n$ 。通过如下方式获得子序列紧邻的下一个排列：从 $a_n, a_{n-1}, …, a_{m+1}$ 中寻找第一个大于 $a_m$ 的数字 $a_j$ , 交换 $a_m, a_j$ ，得到 $a_j, a_{m+1}, …, a_m, .., a_n$ 。新得到的序列应为以 $a_j$ 开头的最大序列。可知交换后的子序列 $a_{m+1}, …, a_m, …, a_n$ 仍为降序，则需要对 $a_{m+1}, …, a_m, …, a_n$ 进行翻转操作，使其变为降序序列。

46. Permutations

算法 1:

算法 2:

猜你喜欢

热点阅读