免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 3492 | 回复: 14

求数列反转距离 [复制链接]

论坛徽章:
0
发表于 2015-09-13 15:58 |显示全部楼层
一组数列如下:
1 2 3 4 5 6 7 8 9 10
3 1 5 2 7 4 9 6 10 8

3 10 8 2 5 4 7 1 6 9
5 2 3 1 7 4 10 8 6 9

8 6 7 9 4 1 3 10 2 5
8 2 7 6 9 1 5 3 10 4

3 9 10 4 1 8 6 7 5 2
2 9 8 5 1 7 3 4 6 10

1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
求5组数列的最小反转距离
反转距离:比如[1,2,5,4,3],[1,2,3,4,5]都是是[2,1,3,4,5]的反转数列,就是3,4,5——>5,4,3  1,2——>2,1[1,2,5,4,3]和[2,1,3,4,5]最小反转距离是2,[1,2,3,4,5]和[2,1,3,4,5]
的最小反转距离是1

5组数列最小反转距离即输出结果如下:
9 4 5 7 0

求大神帮忙。。。

求职 : 软件工程师
论坛徽章:
3
程序设计版块每日发帖之星
日期:2015-10-07 06:20:00程序设计版块每日发帖之星
日期:2015-12-13 06:20:00程序设计版块每日发帖之星
日期:2016-05-05 06:20:00
发表于 2015-09-13 18:40 |显示全部楼层
一个数组的反转子数组的长度可以是 1 吗,反转子数组的数量可以大于 2 吗?

论坛徽章:
0
发表于 2015-09-13 20:03 |显示全部楼层
回复 2# 104359176
不太明白你是什么意思?长度是1,是不是[1,2,3,4,5],3-->3,这个没有意义啊,子数组数量,是什么意思?

   

求职 : 软件工程师
论坛徽章:
3
程序设计版块每日发帖之星
日期:2015-10-07 06:20:00程序设计版块每日发帖之星
日期:2015-12-13 06:20:00程序设计版块每日发帖之星
日期:2016-05-05 06:20:00
发表于 2015-09-14 09:22 |显示全部楼层
本帖最后由 104359176 于 2015-09-14 09:23 编辑

[1,5,4,3,2] == [1] + [5,4,3,2] == [1] + [2,3,4,5]->
[2,1,3,5,4] == [1,2]-> + [3] + [5,4]->

1 个字符反转就是其本身,似乎没有意义,但剩下的数组就有意义了。
如果允许多个子数组,那么算法就完全不同。

论坛徽章:
145
技术图书徽章
日期:2013-10-01 15:32:13戌狗
日期:2013-10-25 13:31:35金牛座
日期:2013-11-04 16:22:07子鼠
日期:2013-11-18 18:48:57白羊座
日期:2013-11-29 10:09:11狮子座
日期:2013-12-12 09:57:42白羊座
日期:2013-12-24 16:24:46辰龙
日期:2014-01-08 15:26:12技术图书徽章
日期:2014-01-17 13:24:40巳蛇
日期:2014-02-18 14:32:59未羊
日期:2014-02-20 14:12:13白羊座
日期:2014-02-26 12:06:59
发表于 2015-09-14 10:30 |显示全部楼层
@104359176 @anna_bi

5组数列最小反转距离即输出结果如下:
9 4 5 7 0

(非0值)演示一下...如何取得最小值

论坛徽章:
8
技术图书徽章
日期:2013-09-30 08:51:28技术图书徽章
日期:2013-12-11 09:26:39白羊座
日期:2013-12-27 15:27:13金牛座
日期:2014-01-06 09:13:05天蝎座
日期:2014-01-21 14:23:28酉鸡
日期:2014-05-09 16:51:12卯兔
日期:2014-08-11 16:49:1515-16赛季CBA联赛之八一
日期:2017-08-14 23:24:57
发表于 2015-09-14 12:37 |显示全部楼层
本帖最后由 xiumu2280 于 2015-09-14 13:30 编辑

楼主还是把 真正的问题说一下吧,哪怕是生物专业性很强的。
感觉这个例子,是楼主所想的解决办法,而不是问题。

第二个为例

3 10 8 2 5 4 7 1 6 9
5 2 3 1 7 4 10 8 6 9

最小反转

1:
3 10 8 2 5 4 7 1 6 9 => 3 5 2 8 10 4 7 1 6 9
5 2 3 1 7 4 10 8 6 9

2:
3 10 8 2 5 4 7 1 6 9 => 3 5 2 1 7 4 10 8 6 9
5 2 3 1 7 4 10 8 6 9

3:
3 10 8 2 5 4 7 1 6 9 => 2 5 3 1 7 4 10 8 6 9
5 2 3 1 7 4 10 8 6 9

4:
3 10 8 2 5 4 7 1 6 9 => 5 2 3 1 7 4 10 8 6 9
5 2 3 1 7 4 10 8 6 9


论坛徽章:
0
发表于 2015-09-14 13:41 |显示全部楼层
回复 4# 104359176
[1,5,4,3,2] == [1] + [5,4,3,2] == [1] + [2,3,4,5]->
[2,1,3,5,4] == [1,2]-> + [3] + [5,4]->

1 个字符反转就是其本身,似乎没有意义,但剩下的数组就有意义了。
如果允许多个子数组,那么算法就完全不同。
如果你把[2,1,3,5,4] 拆分成[1,2]-> + [3] + [5,4]是可以的,但是,如果[1,2]->[2,1],同时[5,4]变成[4,5],那么反转距离就是2,而不是1


   

论坛徽章:
0
发表于 2015-09-14 13:51 |显示全部楼层
回复 6# xiumu2280
Problem

A reversal of a permutation creates a new permutation by inverting some interval of the permutation; (5,2,3,1,4), (5,3,4,1,2), and  (4,1,2,3,5)are all reversals of (5,3,2,1,4). The reversal distance between two permutations  w and y , written d(w,y), is the minimum number of reversals required to transform w into  y (this assumes that w and y have the same length).

Given: A collection of at most 5 pairs of permutations, all of which have length 10.

Return: The reversal distance between each permutation pair.



   

论坛徽章:
0
发表于 2015-09-14 14:09 |显示全部楼层
回复 6# xiumu2280
这就是个问题啊


   

求职 : 软件工程师
论坛徽章:
3
程序设计版块每日发帖之星
日期:2015-10-07 06:20:00程序设计版块每日发帖之星
日期:2015-12-13 06:20:00程序设计版块每日发帖之星
日期:2016-05-05 06:20:00
发表于 2015-09-15 02:18 |显示全部楼层
感觉这个问题的描述太简单了。还是不明白规则。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP