首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

给定n,k,怎么求出1~n排列中所有逆序数为k者

2012-10-21 
给定n,k,如何求出1~n排列中所有逆序数为k者?如题[解决办法]比如说5个数,逆序数为712345 每个位置上对应的

给定n,k,如何求出1~n排列中所有逆序数为k者?
如题

[解决办法]
比如说5个数,逆序数为7

12345 每个位置上对应的最大逆序为 43210,

让第1位为0的话,后面最大逆序为6,因此无解
让第1位为1的话,后面最大逆序为6,有1个解
让第1位为2的话,问题转化为后4个为5
让第1位为3的话,问题转化为后4个为4
让第1位为4的话,问题转化为后4个为3

反正就是这样递归下去,中间用个hash存储算过的,如果已经算过,直接从hash里面读取,其实就相当于DP[i,j]
不过算的比较有目的性,效率可能同动态规划差不多,也许还快一点点吧!

探讨
引用:
按照medie2005所说的逆序表,写了一个计算数量的程序:
C# codestaticvoidMain(string[] args)
...

怎么根据逆序表来计算数量的呢?能不能把思路说一下?

热点排行