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

zltzlt

今天的题目：

给出一个可能包含重复数字的排列，求这些数字的所有排列按字典序排序后该排列在其中的编号。编号从 1 开始。

示例 1：

输入：[1,4,2,2]
输出：3

示例 2：

输入：[1,6,5,3,1]
输：24

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

TJBEST

2019-12-29 22:01:38

我编了一个最傻的，不过但是如果页数过多，计算机内存有限是无法运算的 哈哈。可能我的算法还有优化的可能性，不过时间不是问题，是数字太大电脑算不出来（我用到了阶乘）

1. def fun296(arrayGiven):#可重复那就蛋疼了
   
2.     def count_sort(array):
   
3.         arraysorted = sorted(set(array))#从小打到排序
   
4.         arraycount = []#数量
   
5.         for eachele in arraysorted:
   
6.             arraycount.append(arrayGiven.count(eachele))
   
7.         return (arraysorted,arraycount)
   
8.             
   
9.     def C_mn(m,n):#计算组合数 可以优化
   
10.         A = 1
    
11.         B = 1
    
12.         for i in range(1,n + 1):
    
13.             A =A * (m - i +1)
    
14.             B = B * i
    
15.         return A//B
    
16.         
    
17.     def lessEle(last,arraysorted,arraycount):#找到 并返回比他小的元素列表
    
18.         lessArray = [arraysorted[i] for i in range(0,len(arraysorted)) if arraysorted[i]<last and arraycount[i]>0]
    
19.         return lessArray
    
20.         
    
21.     def chgCount(ele,arraysorted,arraycount):#改变；列表计数
    
22.         index = arraysorted.index(ele)
    
23.         arraycount[index] = arraycount[index]  - 1
    
24.    
    
25.     def cal(arraycount,lenth):#计算
    
26.         result = 1
    
27.         for each in arraycount:
    
28.             result = result * C_mn(lenth,each)
    
29.             lenth = lenth - each
    
30.         return result
    
31.    
    
32.     if arrayGiven == []:
    
33.         return 0
    
34.     (arraysorted , arraycount)= count_sort(arrayGiven)
    
35.     lenth = len(arrayGiven)
    
36.     index = 0
    
37.     result = 1
    
38.     while index < lenth - 1:
    
39.         if index != 0:
    
40.             chgCount(arrayGiven[index - 1],arraysorted,arraycount)
    
41.         else:
    
42.             pass
    
43.         lessArray = lessEle(arrayGiven[index],arraysorted,arraycount)
    
44.         for eachless in lessArray:
    
45.             tempcount = arraycount.copy()
    
46.             chgCount(eachless,arraysorted,tempcount)
    
47.             result = result + cal(tempcount,lenth - 1 - index)
    
48.         index = index + 1
    
49.     return result

复制代码

跳转到最佳答案楼层

Unicorn#

半夜两点写完递归版本，本来想睡了明天再优化，但是没写出来睡不着
第一个是递归版本，支持列表长度<1000，1000时超过递归最大深度
第二个是优化版本，支持列表长度<=2000， 超过2000时数据过大爆栈
猫猫都在我腿上睡着了，溜了溜了
递归版本：

1. def solve2(nums):
   
2.     def transfer(nums):
   
3.         res = []
   
4.         for each in set(nums):
   
5.             res.append((each, nums.count(each)))
   
6.         return res
   
7.     def C(m, n):
   
8.         molecular = 1
   
9.         for i in range(m, m-n, -1):
   
10.             molecular *= i
    
11.         denominator = 1
    
12.         for i in range(n, 0, -1):
    
13.             denominator *= i
    
14.         return int(molecular/denominator)
    
15.     def f(nums):
    
16.         if len(nums) == 1:
    
17.             return 0
    
18.         else:
    
19.             adder = nums[0]
    
20.             n = len(nums)
    
21.             a = f(nums[1:])
    
22.             nums = transfer(nums)
    
23.             choices = list(filter(lambda x:x[0]<adder, nums))
    
24.             b = 0
    
25.             for choice in choices:
    
26.                 count = 1
    
27.                 temp = nums.copy()
    
28.                 index = temp.index(choice)
    
29.                 if temp[index][1] > 1:
    
30.                     temp[index] = (temp[index][0], temp[index][1]-1)
    
31.                 else:
    
32.                     temp.pop(index)
    
33.                 l = n - 1
    
34.                 for each in temp:
    
35.                     count *= C(l, each[1])
    
36.                     l -= each[1]
    
37.                 b += count
    
38.             return a + b
    
39.     return f(nums)+1

复制代码

优化版本：

1. def solve(nums):
   
2.     def C(m, n):
   
3.         molecular = 1
   
4.         for i in range(m, m-n, -1):
   
5.             molecular *= i
   
6.         denominator = 1
   
7.         for i in range(n, 0, -1):
   
8.             denominator *= i
   
9.         return int(molecular/denominator)
   
10.     n = len(nums)
    
11.     res = 1
    
12.     for i in range(2, n+1):
    
13.         temp1 = nums[n-i:]
    
14.         adder = temp1[0]
    
15.         temp2 = [(i, nums.count(i)) for i in set(temp1)]
    
16.         choices = list(filter(lambda x:x[0]<adder, temp2))
    
17.         for choice in choices:
    
18.             count = 1
    
19.             temp3 = temp2.copy()
    
20.             index = temp3.index(choice)
    
21.             if temp3[index][1] > 1:
    
22.                 temp3[index] = (temp3[index][0], temp3[index][1]-1)
    
23.             else:
    
24.                 temp3.pop(index)
    
25.             l = i-1
    
26.             for each in temp3:
    
27.                 count *= C(l, each[1])
    
28.                 l -= each[1]
    
29.             res += count
    
30.     return res

复制代码

TJBEST

我编了一个最傻的，不过但是如果页数过多，计算机内存有限是无法运算的 哈哈。可能我的算法还有优化的可能性，不过时间不是问题，是数字太大电脑算不出来（我用到了阶乘）

1. def fun296(arrayGiven):#可重复那就蛋疼了
   
2.     def count_sort(array):
   
3.         arraysorted = sorted(set(array))#从小打到排序
   
4.         arraycount = []#数量
   
5.         for eachele in arraysorted:
   
6.             arraycount.append(arrayGiven.count(eachele))
   
7.         return (arraysorted,arraycount)
   
8.             
   
9.     def C_mn(m,n):#计算组合数 可以优化
   
10.         A = 1
    
11.         B = 1
    
12.         for i in range(1,n + 1):
    
13.             A =A * (m - i +1)
    
14.             B = B * i
    
15.         return A//B
    
16.         
    
17.     def lessEle(last,arraysorted,arraycount):#找到 并返回比他小的元素列表
    
18.         lessArray = [arraysorted[i] for i in range(0,len(arraysorted)) if arraysorted[i]<last and arraycount[i]>0]
    
19.         return lessArray
    
20.         
    
21.     def chgCount(ele,arraysorted,arraycount):#改变；列表计数
    
22.         index = arraysorted.index(ele)
    
23.         arraycount[index] = arraycount[index]  - 1
    
24.    
    
25.     def cal(arraycount,lenth):#计算
    
26.         result = 1
    
27.         for each in arraycount:
    
28.             result = result * C_mn(lenth,each)
    
29.             lenth = lenth - each
    
30.         return result
    
31.    
    
32.     if arrayGiven == []:
    
33.         return 0
    
34.     (arraysorted , arraycount)= count_sort(arrayGiven)
    
35.     lenth = len(arrayGiven)
    
36.     index = 0
    
37.     result = 1
    
38.     while index < lenth - 1:
    
39.         if index != 0:
    
40.             chgCount(arrayGiven[index - 1],arraysorted,arraycount)
    
41.         else:
    
42.             pass
    
43.         lessArray = lessEle(arrayGiven[index],arraysorted,arraycount)
    
44.         for eachless in lessArray:
    
45.             tempcount = arraycount.copy()
    
46.             chgCount(eachless,arraysorted,tempcount)
    
47.             result = result + cal(tempcount,lenth - 1 - index)
    
48.         index = index + 1
    
49.     return result

复制代码

阴阳神万物主

Unicorn# 发表于 2019-12-29 21:35
明白了
先占楼叭

我用你这个，答案会出错呢。

1. >>> solve([1,1,2,1,1])
   
2. 5
   
3. >>>

复制代码

应该输出 3 呢。
11112->11121->11211->12111->21111
还能有别的排列吗？

阴阳神万物主

抢地板
数学规律，我总算回忆起来了！！！
组合数的计算因为怕超出内存限制，所以就没用杨辉三角，不然还能快一些

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

复制代码

这时间复杂度我就有点不会求了。可有人愿意告知于我呀？

排列数公式：

                               
登录/注册后可看大图

组合数公式：

                               
登录/注册后可看大图

Unicorn#

阴阳神万物主 发表于 2019-12-29 22:04
我用你这个，答案会出错呢。

应该输出 3 呢。

哈哈哈我刚发就知道错了
我在尝试用重复倍率来消掉多余的

Unicorn#

能想出来的最好方案了
才思枯竭 肝到两点
输入数组长度达到1000时超出递归深度限制，1000以内完美运行
明天再写一个列表版的，就没有深度限制了
困死了

1. def solve2(nums):
   
2.     def transfer(nums):
   
3.         res = []
   
4.         for each in set(nums):
   
5.             res.append((each, nums.count(each)))
   
6.         return res
   
7.     def C(m, n):
   
8.         molecular = 1
   
9.         for i in range(m, m-n, -1):
   
10.             molecular *= i
    
11.         denominator = 1
    
12.         for i in range(n, 0, -1):
    
13.             denominator *= i
    
14.         return int(molecular/denominator)
    
15.     def f(nums):
    
16.         if len(nums) == 1:
    
17.             return 0
    
18.         else:
    
19.             adder = nums[0]
    
20.             n = len(nums)
    
21.             a = f(nums[1:])
    
22.             nums = transfer(nums)
    
23.             choices = list(filter(lambda x:x[0]<adder, nums))
    
24.             b = 0
    
25.             for choice in choices:
    
26.                 count = 1
    
27.                 temp = nums.copy()
    
28.                 index = temp.index(choice)
    
29.                 if temp[index][1] > 1:
    
30.                     temp[index] = (temp[index][0], temp[index][1]-1)
    
31.                 else:
    
32.                     temp.pop(index)
    
33.                 l = n - 1
    
34.                 for each in temp:
    
35.                     count *= C(l, each[1])
    
36.                     l -= each[1]
    
37.                 b += count
    
38.             return a + b
    
39.     return f(nums)+1

复制代码

Croper

1. def func296(l:list)->int:
   
2.     counts=[]
   
3.     ret=0
   
4.     t=1
   
5.     i=0
   
6.     for n in reversed(l):
   
7.         p,q=0,len(counts)
   
8.         while p<q:
   
9.             r=(p+q)//2
   
10.             if counts[r][0]==n:
    
11.                 p=r
    
12.                 counts[r][1]+=1
    
13.                 break
    
14.             elif counts[r][0]>n:
    
15.                 q=r
    
16.             else:
    
17.                 p=r+1
    
18.         else:
    
19.             counts.insert(p,[n,1])
    
20. 
    
21. 
    
22.         for count_pair in counts[:p]:
    
23.             ret+=t*count_pair[1]//counts[p][1]
    
24. 
    
25.         i+=1
    
26.         t*=i
    
27.         t//=counts[p][1]
    
28. 
    
29.     return ret+1

复制代码

fan1993423

1. from math import factorial
   
2. from collections import Counter
   
3. from copy import deepcopy
   
4. def fun295(x):
   
5.     if len(x)==len(set(x)):
   
6.         length=len(x)
   
7.         if length<1:
   
8.             return 0
   
9.         x_sort=sorted(x)
   
10.         initialization=0
    
11.         for i in range(length):
    
12.             initialization+=x_sort.index(x[i])*factorial(length-i-1)
    
13.             x_sort.remove(x[i])
    
14.         return initialization+1
    
15.     else:
    
16.         sort_set_x=sorted(list(set(x)))
    
17.         length=len(x)
    
18.         initialization=0
    
19.         d=deepcopy(x)
    
20.         t=1
    
21.         for i in range(length):
    
22.             index=sort_set_x.index(d[i])
    
23.             while index:
    
24.                 k=sort_set_x.pop(0)
    
25.                 k_index=x.index(k)
    
26.                 x.remove(k)
    
27.                 shengxia_x=dict(Counter(x)).values()
    
28.                 x.insert(k_index,k)
    
29.                 for j in shengxia_x:
    
30.                     t*=factorial(j)
    
31.                 initialization+=factorial(len(x)-1)/t
    
32.                 index-=1
    
33.             x.pop(0)
    
34.             sort_set_x=sorted(list(set(x)))
    
35.     return int(initialization)+1

复制代码

fan1993423

另外写个代码少点，但是可能运算量要大的多的代码

1. from itertools import permutations
   
2. def fun295(x):
   
3.     k=sorted(list(set(permutations(x))))
   
4.     return k.index(tuple(x))+1

复制代码

沙里爬

不知道满不满足条件

1. def Factorial(num):
   
2.     s=1
   
3.     for i in range(1,num+1):
   
4.         s *=i
   
5.     return s
   
6. def geshu(num,lst):
   
7.     lst1 = lst.copy()
   
8.     lst1.remove(num)
   
9.     repetition_num=1
   
10.     for i in set(lst1):
    
11.         repetition_num *= Factorial(lst1.count(i))
    
12.     return Factorial(len(lst1))//repetition_num
    
13. def position(num,lst):
    
14.     lst1=list(set(lst))
    
15.     if len(lst1)==1:
    
16.         return 1
    
17.     target = lst1.index(num)
    
18.     k = 0
    
19.     for i in range(target):
    
20.         k += geshu(lst1[i],lst)
    
21.     return k
    
22. def solution(lst):
    
23.     k = 0
    
24.     lenth=len(lst)
    
25.     for i in range(lenth):
    
26.         if len(set(lst))==1:
    
27.             k+=1
    
28.             break
    
29.         else:
    
30.             k += position(lst[0],lst)
    
31.             del lst[0]
    
32.     print(k)

复制代码

hfwei0

1. import math,random
   
2. 
   
3. def fac(lst0):
   
4.     a=1
   
5.     for i in range(len(lst0)):
   
6.         a*=math.factorial(lst0[i])
   
7.     return a
   
8. 
   
9. def pmu(lst):
   
10.     sk=[]
    
11.     sv=[]
    
12.     lst1=lst[:]
    
13.     lst1.sort()
    
14.     n=0
    
15.     total=0
    
16.     while n < len(lst1):
    
17.         tmp=lst1.count(lst1[n])
    
18.         if tmp>1:
    
19.             sk.append(lst1[n])
    
20.             sv.append(tmp)
    
21.         n+=tmp
    
22.     for i in range(len(lst)):
    
23.         temp=lst1.index(lst[i])
    
24.         if lst[i] in sk:
    
25.             stmp=sk.index(lst[i])
    
26.             sv[stmp]-=1
    
27.             if sv[stmp] == 1:
    
28.                 sk.pop(stmp)
    
29.                 sv.pop(stmp)
    
30.         total+=temp*(math.factorial(len(lst1)-1)/fac(sv))
    
31.         lst1.pop(temp)
    
32.     return int(total+1)
    
33. c=[]
    
34. for i in range(300):
    
35.     c.append(random.randint(1,10))
    
36. print(pmu(c))

复制代码

print(pmu(c))[/code]只能到300。。。

_2_

fan1993423 发表于 2019-12-30 15:07
另外写个代码少点，但是可能运算量要大的多的代码

这个6诶

danteer

1. def justcount(list1):
   
2.     import itertools
   
3.     list2 = list1.copy()
   
4.     list2.sort()
   
5.     list3 = list(itertools.permutations(list2,len(list2)))
   
6.     temp = 0
   
7.     while temp < len(list3):
   
8.         if list3.count(list3[temp]) > 1:
   
9.             temp2 = list3.count(list3[temp])
   
10.             temp3 = list3[temp]
    
11.             for i in range(temp2):
    
12.                 list3.remove(temp3)
    
13.             list3.insert(temp,temp3)
    
14.         temp += 1
    
15.     return list3.index(tuple(list1))+1

复制代码

zltzlt

Unicorn# 发表于 2019-12-30 01:58
能想出来的最好方案了
才思枯竭 肝到两点
输入数组长度达到1000时超出递归深度限制，1000以内完美运行

zltzlt

fan1993423 发表于 2019-12-30 14:39

解答错误

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

Unicorn#

zltzlt 发表于 2019-12-30 21:39

递归那个快是因为你的测试数据太短了...
我这边测试在输入列表长度超过两百时优化版就有明显优势了（还不会被最大深度限制）

fan1993423

zltzlt 发表于 2019-12-30 21:40
解答错误

输入：[3,2,2,1,1]

不好意思，刚看了下，忘了重新对t还原为1，在32行添加一句t=1

1. from math import factorial
   
2. from collections import Counter
   
3. from copy import deepcopy
   
4. def fun295(x):
   
5.     if len(x)==len(set(x)):
   
6.         length=len(x)
   
7.         if length<1:
   
8.             return 0
   
9.         x_sort=sorted(x)
   
10.         initialization=0
    
11.         for i in range(length):
    
12.             initialization+=x_sort.index(x[i])*factorial(length-i-1)
    
13.             x_sort.remove(x[i])
    
14.         return initialization+1
    
15.     else:
    
16.         sort_set_x=sorted(list(set(x)))
    
17.         length=len(x)
    
18.         initialization=0
    
19.         d=deepcopy(x)
    
20.         t=1
    
21.         for i in range(length):
    
22.             index=sort_set_x.index(d[i])
    
23.             while index:
    
24.                 k=sort_set_x.pop(0)
    
25.                 k_index=x.index(k)
    
26.                 x.remove(k)
    
27.                 shengxia_x=dict(Counter(x)).values()
    
28.                 x.insert(k_index,k)
    
29.                 for j in shengxia_x:
    
30.                     t*=factorial(j)
    
31.                 initialization+=factorial(len(x)-1)/t
    
32.                 t=1
    
33.                 index-=1
    
34.             x.pop(0)
    
35.             sort_set_x=sorted(list(set(x)))
    
36.     return int(initialization)+1

复制代码

阴阳神万物主

我五楼的地板，代码已更新出来了

阴阳神万物主

Unicorn# 发表于 2019-12-29 21:35
半夜两点写完递归版本，本来想睡了明天再优化，但是没写出来睡不着
第一个是递归版本，支持列 ...

我怀疑你的组合数计算有点小问题。

1. >>> def C(m, n):
   
2.         molecular = 1
   
3.         for i in range(m, m-n, -1):
   
4.             molecular *= i
   
5.         denominator = 1
   
6.         for i in range(n, 0, -1):
   
7.             denominator *= i
   
8.         return int(molecular/denominator)
   
9. 
   
10. >>> get = C(200,100)
    
11. >>> x = y = z = 1
    
12. >>> for i in  range(200,0,-1):
    
13.         x *= i
    
14. 
    
15.         
    
16. >>> for i in range(100,0,-1):
    
17.         y *= i
    
18. 
    
19.         
    
20. >>> for i in range(200-100,0,-1):
    
21.         z *= i
    
22. 
    
23.         
    
24. >>> (x//(y*z)) - get
    
25. 484929433446296225432192901808955449760872
    
26. >>>  

复制代码

                               
登录/注册后可看大图

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