一个有趣的算法题(1)

编程果然是一项需要学到老的技能，放下手1个礼拜不码代码就感觉有种陌生感了。 所以没事刷刷存在感还是很有必要的，防止中年痴呆！

好了，废话不多说，第一次带来的一道题很有去，来自于codewars，详情请看页面描述。

题目大概意思就是149本身是一个素数，然后由149构成的3个数字：1，4，9可以排列成419，491，941三个素数。小于1000的数字中，有3个素数可以由自身排列成3个其他的素数，比如：

149 ==> 419 ==> 491 ==> 941
179 ==> 197 ==> 719 ==> 971
379 ==> 397 ==> 739 ==> 937

如果是只有2个素数的话，那么小于1000的情况会有9个：

113 ==> 131 ==> 311
137 ==> 173 ==> 317
157 ==> 571 ==> 751
163 ==> 613 ==> 631
167 ==> 617 ==> 761
199 ==> 919 ==> 991
337 ==> 373 ==> 733
359 ==> 593 ==> 953
389 ==> 839 ==> 983

如果排列只有1个素数的话，会有34个情况： [13, 17, 37, 79, 107, 127, 139, 181, 191, 239, 241, 251, 277, 281, 283, 313, 347, 349, 367, 457, 461, 463, 467, 479, 563, 569, 577, 587, 619, 683, 709, 769, 787, 797] 两位数很简单，只要反转一下是素数就行，比如素数13，那么31同样也是素数，所以是符合排列只有1个素数的情况，三位数就复杂点了，请自行举例。

我们还是以149这个素数为例，由1，4，9三个数字排列形成的419, 491, 941是符合要求的，那么149，419, 491, 941这几个数字就是一个set，由149这个最小值作为代表，代表这组set。

然后，题目的notes规定，原始的素数，比如149，这个数本身不计算为一个排列情况，也就是由1，4，9三个数字形成的permutation数值为3个，也就是149排列形成的素数个数是3个（并不包括149本身），另外0开头数字无效。

题目的任务就是写个函数permutational_primes，这个函数有两个参数，n_max是上限值，k_perms是permutation的数值，由这两个参数，函数需要计算并返回包含3个数字的数组：

1. 在n_max范围内符合permutation数值的素数个数
2. 符合要求的最小值
3. 符合要求的最大值

比如：

permutational_primes(1000, 3) ==> [3, 149, 379]
''' 3 primes with 3 permutations below 1000, smallest: 149, largest: 379 '''

permutational_primes(1000, 2) ==> [9, 113, 389]
''' 9 primes with 2 permutations below 1000, smallest: 113, largest: 389 '''

permutational_primes(1000, 1) ==> [34, 13, 797]
''' 34 primes with 1 permutation below 1000, smallest: 13, largest: 797 '''

permutational_primes(1000, 3)前面已经说了，小于1000的素数中，149，179，379这3个数的排列中正好有3个是素数，符合函数的第二个参数3的要求，所以这个函数的解的第一个值就是3，这个3个值中，最小值149，最大值379，所以整个函数的解是[3,149,379] 同理，permutational_primes(1000,2)的解是[9,113,389],permutational_primes(1000,1)的解是[34,13,797]

所以，最后的任务就是需要把这个函数写出来，对任意的两个参数n_max,k_perms就可计算出结果来。

像这些题目，逻辑其实不难，随便写一个什么循环判断一下就可以出结果，但是因为涉及到要pass系统的运算时间要求，所以暴力法是不可能能通过的,如果你觉得你很简单就写出来，那么可以试着提交上去，估计大概率是timeout，需要对函数进行优化设计,降低复杂度才能通过。从题目的页面下方也可以看出，能通过的人数并不多，只有几十个人，python50多人，js18人，ruby更是只有5人。虽然系统定义为一个4kyu的题目，也就是中等便难，但是我认为定义为一个3kyu的题目也不为过。

说了半天，只是做了介绍，也并不想在本文就贴上答案，毕竟本人不才，这道题我反正是刷了1-2天都没解出来，后来灵光一炸才搞定的。所以也希望朋友们先自己思考去解解看试试，等下次再贴答案，而且贴的也是ruby的答案，python就自己按照同样的思路去实现吧。（友情提示：ruby的解法核心代码只需要一行（你没看错，前面说的那么大一堆只需要一行就搞定），总代码只需要3行就搞定）