[已解决]Python：每日一题 296

zltzlt

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

我知道，不想搞太长的测试数据

Unicorn#

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

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

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

zltzlt

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

解答错误

输入：[10,10,10,10,9,8,7,6,5,4,3,2,1]
输出：29151360
预期结果：259459200

zltzlt

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

解答错误

输入：[2,6,4,5,8,1,7,3]
输出：8210
预期结果：8228

zltzlt

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

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

zltzlt

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

解答错误

输入：[3,2,2,1,1]
输出：33
预期结果：30

zltzlt

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

输入 [3,5,5,6,7,3,2,1] 超时

阴阳神万物主

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

输入：[10,10,10,10,9,8,7,6,5,4,3,2,1]

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

zltzlt

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

你理解错了。

百度百科：字典序

_2_

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

百度百科：字典序

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

zltzlt

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

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

zltzlt

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

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

阴阳神万物主

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

百度百科：字典序

我理解错的不是字典序，而是：你原来不是要把那些数字先按顺序组成一个数字，再看后来这个数字的排号，是直接看这个排列的排号。
我一开始理解的：
结果你想要的：
既然如此就这么整：

1. yh = [[1]]
   
2. def solve(n:'可能包含重复数字的排列')->'编号':
   
3.     def a(n,m):#m<=n
   
4.         res = 1
   
5.         for i in range(n,n-m,-1):
   
6.             res *= i
   
7.         return res
   
8.     def c(n,m):#m<=n
   
9.         res = 1
   
10.         for i in range(n,m,-1):
    
11.             res *= i
    
12.         for i in range(n-m,1,-1):
    
13.             res //= i
    
14.         return res
    
15.     def cy(n,m):
    
16.         global yh
    
17.         while len(yh) <= n:
    
18.             ad = [1]+[yh[-1][x]+(yh[-1][x+1] if x+1 < len(yh[-1]) else 0)for x in range(len(yh[-1]))]
    
19.             yh.append(ad)
    
20.         return yh[n][m]
    
21.    
    
22.     d = n#[str(x) for x in n]
    
23.     b = dict([(each,d.count(each)) for each in set(d)])
    
24.     res = 1
    
25.     le = len(d)
    
26.     for i in range(le):
    
27.         dlt = 0
    
28.         le -= 1
    
29.         for j in b:
    
30.             if(b[j] and j<d[i]):
    
31.                 each = 0
    
32.                 b[j] -= 1
    
33.                 an = 0
    
34.                 for n in b:
    
35.                     if b[n] > 1:
    
36.                         each = each*c(le,b[n]) if each else c(le,b[n])
    
37.                         le -= b[n]
    
38.                         dlt -= b[n]
    
39.                     elif b[n]:
    
40.                         an += 1
    
41.                 each = each*a(an,an) if each else a(an,an)
    
42.                 le -= dlt
    
43.                 dlt = 0
    
44.                 res += each
    
45.                 b[j] += 1
    
46.         b[d[i]] -= 1
    
47.     return res
    
48. 
    
49. if __name__ == '__main__':
    
50.     '''
    
51.     print('示例1 输出：',solve([1,4,2,2]))
    
52.     print('示例2 输出：',solve([1,6,5,3,1]))
    
53.     print('自测 6 输出：',solve([1,2,2,1,1]))
    
54.     print('自测 30 输出：',solve([3,2,2,1,1]))'''
    
55.     #print('自测大数据，全排列数为c(2000,1000) 输出：',solve([1,2]*1000))
    

复制代码

阴阳神万物主

所以，用时呢？？

zltzlt

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

105 ms

776667

1. from itertools import permutations
   
2. 
   
3. def fun296(x):
   
4.     list_x = []
   
5.     for i in permutations(x):
   
6.         if list(i) not in list_x:
   
7.             list_x.append(list(i))
   
8.     return sorted(list_x).index(x)+1

复制代码