[已解决]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
你理解错了。

百度百科：字典序

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

yh = [[1]]
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 = [1]+[yh[-1][x]+(yh[-1][x+1] if x+1 < len(yh[-1]) else 0)for x in range(len(yh[-1]))]
            yh.append(ad)
        return yh[n][m]
    
    d = n#[str(x) for x in 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[j] and j<d[i]):
                each = 0
                b[j] -= 1
                an = 0
                for n in b:
                    if b[n] > 1:
                        each = each*c(le,b[n]) if each else c(le,b[n])
                        le -= b[n]
                        dlt -= b[n]
                    elif b[n]:
                        an += 1
                each = each*a(an,an) if each else a(an,an)
                le -= dlt
                dlt = 0
                res += each
                b[j] += 1
        b[d[i]] -= 1
    return res

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

阴阳神万物主

所以，用时呢？？

zltzlt

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

105 ms

776667

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