论坛 › Python交流 › Python：每日一题 296

zltzlt 发表于 2019-12-31 17:57:14

Unicorn# 发表于 2019-12-30 21:43
递归那个快是因为你的测试数据太短了...
我这边测试在输入列表长度超过两百时优化版就有明显优势了（还 ...

我知道，不想搞太长的测试数据{:10_277:}

Unicorn# 发表于 2019-12-31 18:56:42

阴阳神万物主 发表于 2019-12-31 01:33
我怀疑你的组合数计算有点小问题。

严格按照定义公式计算的组合数比你的大好多。

我寻思这俩是等价的鸭
我比较喜欢我的那个

zltzlt 发表于 2019-12-31 20:55:39

阴阳神万物主 发表于 2019-12-29 22:05
抢地板
数学规律，我总算回忆起来了！！！
组合数的计算因为怕超出内存限制，所以就没用杨辉三角，不然还 ...

解答错误

输入：
输出：29151360
预期结果：259459200

zltzlt 发表于 2019-12-31 21:22:03

沙里爬 发表于 2019-12-30 18:22
不知道满不满足条件

解答错误

输入：
输出：8210
预期结果：8228

zltzlt 发表于 2019-12-31 21:22:44

_2_ 发表于 2019-12-30 19:47
这个6诶

表面上看代码量少，实际不符合要求

zltzlt 发表于 2019-12-31 21:23:27

hfwei0 发表于 2019-12-30 18:58
print(pmu(c))只能到300。。。

解答错误

输入：
输出：33
预期结果：30

zltzlt 发表于 2019-12-31 21:23:53

danteer 发表于 2019-12-30 21:15


输入 超时

阴阳神万物主 发表于 2019-12-31 23:01:11

本帖最后由 阴阳神万物主 于 2019-12-31 23:06 编辑

zltzlt 发表于 2019-12-31 20:55
解答错误

输入：

恩姆，不是说按字典序排号么？
输入：
按照字典序，也是数字大小顺序，该排 6
1089->1098->9108->8910->9108->9810
不是说数字大排在前面就大。
你看看你认为对的那个程序，是不是返回的 3
的全排列数为 C(13,4)*A(9,9) = 259459200
而这个排列显然不是最大的那个，至少还有以2开头的数

zltzlt 发表于 2020-1-1 10:16:44

阴阳神万物主 发表于 2019-12-31 23:01
恩姆，不是说按字典序排号么？
输入：
按照字典序，也是数字大小顺序，该排 6


你理解错了。

百度百科：字典序

_2_ 发表于 2020-1-1 11:40:43

zltzlt 发表于 2020-1-1 10:16
你理解错了。

百度百科：字典序

弄一些一般人不知道的概念

zltzlt 发表于 2020-1-1 12:23:00

_2_ 发表于 2020-1-1 11:40
弄一些一般人不知道的概念

这个概念其实在编程中比较常见

zltzlt 发表于 2020-1-1 12:23:59

_2_ 发表于 2020-1-1 11:40
弄一些一般人不知道的概念

“字典序” 其实很好理解的。

阴阳神万物主 发表于 2020-1-1 13:54:17

本帖最后由 阴阳神万物主 于 2020-1-1 14:02 编辑

zltzlt 发表于 2020-1-1 10:16
你理解错了。

百度百科：字典序
我理解错的不是字典序，而是：你原来不是要把那些数字先按顺序组成一个数字，再看后来这个数字的排号，是直接看这个排列的排号。
我一开始理解的：
结果你想要的：
既然如此就这么整：
yh = []
def solve(n:'可能包含重复数字的排列')->'编号':
    def a(n,m):#m<=n
      res = 1
      for i in range(n,n-m,-1):
            res *= i
      return res
    def c(n,m):#m<=n
      res = 1
      for i in range(n,m,-1):
            res *= i
      for i in range(n-m,1,-1):
            res //= i
      return res
    def cy(n,m):
      global yh
      while len(yh) <= n:
            ad = ++(yh[-1] if x+1 < len(yh[-1]) else 0)for x in range(len(yh[-1]))]
            yh.append(ad)
      return yh
   
    d = n#
    b = dict([(each,d.count(each)) for each in set(d)])
    res = 1
    le = len(d)
    for i in range(le):
      dlt = 0
      le -= 1
      for j in b:
            if(b and j<d):
                each = 0
                b -= 1
                an = 0
                for n in b:
                  if b > 1:
                        each = each*c(le,b) if each else c(le,b)
                        le -= b
                        dlt -= b
                  elif b:
                        an += 1
                each = each*a(an,an) if each else a(an,an)
                le -= dlt
                dlt = 0
                res += each
                b += 1
      b] -= 1
    return res

if __name__ == '__main__':
    '''
    print('示例1 输出：',solve())
    print('示例2 输出：',solve())
    print('自测 6 输出：',solve())
    print('自测 30 输出：',solve())'''
    #print('自测大数据，全排列数为c(2000,1000) 输出：',solve(*1000))

阴阳神万物主 发表于 2020-1-1 14:04:15

所以，用时呢？？

zltzlt 发表于 2020-1-1 14:05:34

阴阳神万物主 发表于 2020-1-1 14:04
所以，用时呢？？

105 ms

776667 发表于 2020-9-17 11:35:52

from itertools import permutations

def fun296(x):
    list_x = []
    for i in permutations(x):
      if list(i) not in list_x:
            list_x.append(list(i))
    return sorted(list_x).index(x)+1

查看完整版本: Python：每日一题 296