我正在寻找一种算法,可以将数字映射到序列的唯一排列.由于类似的问题,快速置换 - >数字 - >置换映射算法,我已经发现了Lehmer代码和阶乘数系统,但该问题并未涉及序列中存在重复元素的情况.
例如,采用序列'AAABBC'.有6个!= 720种方式可以安排,但我相信只有6种!/(3!*2!*1!)= 60这个序列的独特排列.在这些情况下,如何将数字映射到排列？
编辑:将术语"设置"更改为"序列".
给定一个数组说"bca",我需要找到排列数量大于给定排列的排列数.
因此,在该示例中,cab,cba是更大的排列.因此答案是2.
我尝试通过查找数组的词典排名来解决问题,但我无法为说法设计一个有效的算法.
任何帮助/指针在正确的方向是值得赞赏的!
这是一个面试问题.让按字典顺序列出排列.例如123,132,213,231,312,321.给定排列在这样的列表中找到它的索引.例如,置换索引213是2(如果我们从0开始).
平凡地说,我们可以使用next_permutation算法以字典顺序生成下一个排列,但它导致O(N!)解,这显然是不可行的.有没有更好的解决方案？
给定一个长度不超过25个字符的输入字符串,由字符AZ组成,在输入字符串的所有可能字符串的按字母顺序排序的列表中输出其索引.输入字符串不区分大小写.输入字符可以重复.该应用程序必须在不到500毫秒的时间内完成并占用少于1GB的内存.
乍一看,没有任意精度数学库,这看起来是不可能的.最坏的情况输入是25个独特的字符,结果是25!可能的字谜.25!是数量级大于2 ^ 64.由于索引和字符串之间的关系不是直接的并且必须计算,因此无法简单地将字符串转换为数字.
这来自我前几天接受的采访挑战.我无法为他们提出解决方案,他们坚持认为确实有一个很好的解决方案......