登录
注册
关注
TOP

查看: 1195|回复: 8
收起左侧

[二分/排序/搜索] 求助一道排序算法题,脑阔疼!

[复制链接] |只看干货 |刷题, 二分/排序/搜索

升级   61.5%


分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (13)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
一个大于等于3的数组 然后是乱序的 其中的任意三个数字(不一定连续) a,b,c 可以换序变成b,c,a, 可以换很多次,那这个数组里的数可以不可以通过这个规律把它变成升序排列呢?

上一篇:求大家帮忙看一个题
下一篇:Permutation回溯法递归的visulization

升级   82.68%

magicsets 2020-2-22 19:40:10 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   99% (1262)
 
 
0% (8)    👎
本帖最后由 magicsets 于 2020-2-22 19:41 编辑

楼上所说的逆序对的判定方法是正确的,但如果要解释为什么的话需要一些基本的群论知识,这里稍微展开一下..

为了简化讨论我们假定数组里没有重复元素(而且有重复元素也没法做到题目所要求的“升序排列”)

1.

三元素轮换 "a,b,c -> b,c,a"(并且其他元素位置不变)是置换(permutation)的特例,叫做3-cycle,可以记作 (a, b, c)

比如说如果数组长度为4的话,记数组元素的位置为1,2,3,4,那么有12种3-cycle:

(1, 2, 3): 1号元素换到2号,2号换到3号,3号换到1号,4号不动
(1, 3, 2): 1号元素换到3号,3号换到2号,2号换到1号,4号不动
(1, 2, 4): 1号元素换到2号,2号换到4号,3号不动,4号换到1号
...

2.

先不考虑3-cycle,考虑一个长度为 n 的数组,其有 n! 种重排方式

那么所有重排方式构成一个拥有 n! 个元素的置换群,称为对称群(symmetric group),记作 Sn

3.

定理:对于长度为n的数组,考虑所有可能的三元素轮换的组合,所得到的重排的集合一定是n阶 “交错群”(alternating group),记作An,其是Sn中所有偶置换构成的一个子集(准确来说是个正规子群),元素数量一定为 n! / 2

这里涉及的一个重要概念就是置换的奇偶性,参考:
https://www.cnblogs.com/1036464679hxl/p/7845814.html

相关证明可以参考这个notes里面的Lemma 3.1:
https://kconrad.math.uconn.edu/blurbs/grouptheory/genset.pdf
其实notes里面还有更强的一个结论(Theorem 3.4):每次只需要轮换相邻的三个元素,就可以得到An中的任意重排

4.

现在,我们考虑从数组原来的顺序到升序的置换 P,原问题的就等价于问 P 是否在 An 中

举个例子,考虑长度为4的数组 [40 30 10 20],那么目标的升序数组就是 [10, 20, 30, 40]

那么对应的置换 P 的轮换表示就是 (1,4,2,3)
也就是1号位置的40要换到4号位置去,2号位置的30要换到3号位置,3号位置的10要换到1号位置,4号位置的20要换到2号位置

然而 A4 的12个置换中并不包含 (1, 4, 2, 3):
https://groupprops.subwiki.org/wiki/A4_in_S4

所以 [40 30 10 20] 并不能通过三元素轮换的方法转换到 [10 20 30 40]

5.

现在是最后一步了,给定一个长度为 n 的数组,如何判定是否可以得到升序?

两种方法,都是nlog(n)时间:

(1) 将原数组排序 -> 求置换 P -> 判定 P 是否是偶置换

排序O(n log(n)),求置换及判定 O(n),参考:https://stackoverflow.com/questi ... ty-of-a-permutation

(2) 将原数组归并排序 -> 过程中数逆序对数量 -> 判定奇偶性

也是O(n log(n))。至于为什么逆序对数量的奇偶性与置换 P 的奇偶性一致,上面写的第3点的那个cnblogs链接中有证明


补充内容 (2020-2-23 05:30):
第1部分中“12种3-cycle” -> “8种3-cycle”

评分

参与人数 4大米 +24 收起 理由
anhpp + 2 给你点个赞!
苏糖糖糖 + 1 给你点个赞!
14417335 + 20
Shilcare + 1 赞一个!

查看全部评分

回复

使用道具 举报

升级   40.5%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (59)
 
 
4% (3)    👎
当然不可以了,(3,2,1),你怎么转都不是升序啊

评分

参与人数 1大米 +1 收起 理由
14417335 + 1

查看全部评分

回复

使用道具 举报

升级   61.5%

 楼主| 苏糖糖糖 2020-2-22 00:14:25 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (13)
 
 
0% (0)    👎
凤歌打狐狸 发表于 2020-2-22 00:07
当然不可以了,(3,2,1),你怎么转都不是升序啊

对 你说的这个case是不可以的 但是问题是给定一个任意的要判断一下是否可以~
回复

使用道具 举报

头像被屏蔽
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

升级   40.5%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (59)
 
 
4% (3)    👎
苏糖糖糖 发表于 2020/02/22 00:14:25
对 你说的这个case是不可以的 但是问题是给定一个任意的要判断一下是否可以~
那这个也很简单,你把所有乱序对数加起来,如果是偶数就可以,奇数就不可以,最粗暴的count就是O(n^2)了,也可以用排序来做那就是O(n log n),至于能不能O(n)你可以想一想🤔️

评分

参与人数 1大米 +1 收起 理由
苏糖糖糖 + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

升级   40.5%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (59)
 
 
4% (3)    👎
magicsets 发表于 2020/02/22 19:40:10
楼上所说的逆序对的判定方法是正确的,但如果要解释为什么的话需要一些基本的群论知识,这里稍微展开一下..

为了简化讨...
哈哈哈,我就说了个解答,你就把证明搬来了,我觉得这里大部分人不太在意背后的数学原理,其实数学才是算法里的黑魔法👌
回复

使用道具 举报

升级   61.5%

 楼主| 苏糖糖糖 2020-2-23 01:52:54 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (13)
 
 
0% (0)    👎
magicsets 发表于 2020-2-22 19:40
楼上所说的逆序对的判定方法是正确的,但如果要解释为什么的话需要一些基本的群论知识,这里稍微展开一下.. ...

您真是太6了!!!让我想起了好几年前学的抽象代数hhh
回复

使用道具 举报

升级   1.73%

huntersjm 2020-2-23 15:29:22 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (116)
 
 
0% (0)    👎
你得每次变化都是 逆序数为偶数,所以如果你原先的数据的逆序是奇数,就不可能通过这种方法排序。同理,如果逆序数为2,可以通过构造的方法,保持逆序数一直减少,就能最终变成0。这里存在两种可能,一种是 3,1,2,这种可以通过两次旋转得到1,2,3,是的逆序数减少2,另一种是,3,2,1 可以通过一次旋转得到1,3,2也能减少逆序数2.总之,只要存在乱序,就能保持逆序数一直减少,直到 逆序数%2。由此可能,充分必要条件是逆序数为偶数。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

论坛导航
快速回复 返回顶部 返回列表