- 主题:求一个题目的非暴力算法
题目： 给定前N个自然数的一个乱序排列， 比如 3 1 2， 求能让其顺序排列的最小操作次数。其“操作”只有一种，即对任何一个子序列反序。 所以，312，需要操作两次 312-》321-》123。输出2.
输入4321 ，输出1.
目前只想到一个比较费时间， 特别费空间的算法：
原始输入序列压入队列，同时记录操作次数为0。
while （队列非空）：
弹出队列头和当前操作次数。
两重循环遍历该当前序列的所有子序列：
反序该子序列
if（顺序了）：
返回当前操作次数 + 1
结束
else：
把（得到的新序列，当年操作次数+1）压入队列
有没有经济一点的办法？
--
FROM 81.157.216.*
你是要找两个点（312 和123）的最短距离。可以用网络图的最短距离查找的算法。
【 在 SHENOK 的大作中提到: 】
: 题目： 给定前N个自然数的一个乱序排列， 比如 3 1 2， 求能让其顺序排列的最小操作次数。其“操作”只有一种，即对任何一个子序列反序。 所以，312，需要操作两次 312-》321-》123。输出2.
: 输入4321 ，输出1.
:
: ...................
--
FROM 68.97.41.*
是要首先建立一个图吗？
3个数的序列就是1000个节点，10个数就是10亿个节点？
然后求最短路径？
【 在 cafitren 的大作中提到: 】
: 你是要找两个点（312 和123）的最短距离。可以用网络图的最短距离查找的算法。
:
--
FROM 81.157.216.*
是的，但是你不需要显式地事先把图建起来，可以边算距离边加点。
最坏情况可能会相当于把这些节点都建了，但是平均情况应该只要建一小部分。
【 在 SHENOK 的大作中提到: 】
: 是要首先建立一个图吗？
:
: 3个数的序列就是1000个节点，10个数就是10亿个节点？
: ...................
--
FROM 68.97.41.*
感觉跟我上面的算法等价啊
我那个就是每次走一步， 走到了就退出， 没走到就要记录现场，然后继续。。。。。
【 在 cafitren 的大作中提到: 】
: 是的，但是你不需要显式地事先把图建起来，可以边算距离边加点。
: 最坏情况可能会相当于把这些节点都建了，但是平均情况应该只要建一小部分。
:
--
FROM 81.157.216.*
要是等价的话，那现在的算法就应该是最经济的了。你可能可以把序列改成哈希值什么玩意的来提升效率，但是不会有复杂度的改进了。
【 在 SHENOK 的大作中提到: 】
: 感觉跟我上面的算法等价啊
: 我那个就是每次走一步， 走到了就退出， 没走到就要记录现场，然后继续。。。。。
:
--
FROM 68.97.41.*
感觉需要用上动态规划
【 在 SHENOK 的大作中提到: 】
: 题目： 给定前N个自然数的一个乱序排列， 比如 3 1 2， 求能让其顺序排列的最小操作次数。其“操作”只有一种，即对任何一个子序列反序。 所以，312，需要操作两次 312-》321-》123。输出2.
: 输入4321 ，输出1.
:
: ...................
--
FROM 114.249.23.*
如果不需要自己造轮子，工程上可以这样，伪码：
a = '312'
b = sort(a) # 直接造出要最后的字符串123
求从 a 变换成 b 的步数，这是标准的编辑距离算法，有python实现的，也可以直接掉包
pip install python-Levenshtein
import Levenshtein as Le
step = Le.distance(a,b)
【 在 SHENOK 的大作中提到: 】
: 题目： 给定前N个自然数的一个乱序排列， 比如 3 1 2， 求能让其顺序排列的最小操作次数。其“操作”只有一种，即对任何一个子序列反序。 所以，312，需要操作两次 312-》321-》123。输出2.
: 输入4321 ，输出1.
:
: ...................
--
FROM 123.113.63.*
这个好像不是吧，对于楼主的问题
12345和54321的距离是1
【 在 walkerbj 的大作中提到: 】
: 如果不需要自己造轮子，工程上可以这样，伪码：
: a = '312'
: b = sort(a) # 直接造出要最后的字符串123
: ...................
--
FROM 114.249.23.*
bb = reverse(b)
算2个step，取min的
【 在 littleSram 的大作中提到: 】
: 这个好像不是吧，对于楼主的问题
: 12345和54321的距离是1
--
FROM 123.113.63.*