next permutation的推导

请问大家，next permutation这道题是如何推导出那个方法的。感觉看答案再写就很容易，但是如何解释这个思路啊？ 求小伙伴指导一下

这题我自己做出来的, 所以印象很深.

肯定是从base case开始推, 你想, 如果是1234, 那么下一个你自己也知道是 1243. 有任何规律吗? 好像看不出来.

再想edge case, 最后一个是4321, 这个是没有next perm的, 或者说下一个就回到最初的起点1234了,  呆呆的站在镜子前(咦?)

怎么硕呢, 再找几个case - 2314 -> 2341, 3412 -> 3421

然后发现.. 似乎应该是increasing sequence就可以做next perm. 似乎也很符合道理, 因为后面有大的你就可以提前放.

那么为了保证下一个perm是最小的, 应该去找最后一个出现的increasing sequence. 所以找的是 n[i] < n[i + 1] for i in [0, n - 1]

然后把后面大的这个提前, 然后后面再排序就好.

然后如果没有的话就说明是最大的了.. 就这样

肥宅快乐水 发表于 2018-8-31 23:04
这题我自己做出来的, 所以印象很深.

肯定是从base case开始推, 你想, 如果是1234, 那么下一个你自己也知 ...

ls说的太详细了，一下就懂了。赞一个

lawrence0126 发表于 2018-9-1 01:47
ls说的太详细了，一下就懂了。赞一个

显然你最后一个increasing sequence之后一定是单调递减, 否则还可以换后面的.

所以一个问题是调换过之后怎么不用sort,  基本上和merge差不多.

举例 35421, 先交换53, -> 53421. 现在知道[421]是递减, 问题是怎么O[n] 做[1234]

一般是先把当前位置的一直交换到该出现的位置, 然后再前后调转, 基本上算insertion sort.

所以先[4321] 然后再 [1234].

补充内容 (2018-9-1 02:06):
太客气了, 互相学习.

肥宅快乐水 发表于 2018-8-31 07:04
这题我自己做出来的, 所以印象很深.

肯定是从base case开始推, 你想, 如果是1234, 那么下一个你自己也知 ...

1234->4321都写出来就懂了

为什么到处都有你。

vtiaocao 发表于 2018-9-1 03:42
1234->4321都写出来就懂了

为什么到处都有你。

brute force才是正解

{:8_248:}{:8_247:}

我是爱做题的人.. 来做这个
http://www.1point3acres.com/bbs/ ... p;page=1#pid4459195

肥宅快乐水 发表于 2018-8-31 12:14
brute force才是正解

毕竟每周2个contest的大佬……我上次掉了几百名 不想做了……

vtiaocao 发表于 2018-9-1 04:41
毕竟每周2个contest的大佬……我上次掉了几百名 不想做了……

都怪lgd，打破了偶数年的传统，僵硬

肥宅快乐水 发表于 2018-8-31 14:03
都怪lgd，打破了偶数年的传统，僵硬

技不如人甘拜下风

vtiaocao 发表于 2018-9-1 06:04
技不如人甘拜下风

嚯，你好！打得不错，我选择死亡