Python：每日一题 296,Python交流,技术交流,鱼C论坛

zltzlt 发表于 2019-12-29 20:50:09

Python：每日一题 296

今天的题目：

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

示例 1：

输入：
输出：3
示例 2：

输入：
输：24

{:10_298:}欢迎大家一起答题！{:10_298:}

Unicorn# 发表于 2019-12-29 21:35:35

本帖最后由 Unicorn# 于 2019-12-30 13:06 编辑

半夜两点写完递归版本，本来想睡了明天再优化，但是没写出来睡不着{:10_262:}
第一个是递归版本，支持列表长度<1000，1000时超过递归最大深度
第二个是优化版本，支持列表长度<=2000，超过2000时数据过大爆栈
猫猫都在我腿上睡着了，溜了溜了{:10_335:}
递归版本：
def solve2(nums):
def transfer(nums):
   res = []
   for each in set(nums):
         res.append((each, nums.count(each)))
   return res
def C(m, n):
   molecular = 1
   for i in range(m, m-n, -1):
         molecular *= i
   denominator = 1
   for i in range(n, 0, -1):
         denominator *= i
   return int(molecular/denominator)
def f(nums):
   if len(nums) == 1:
         return 0
   else:
         adder = nums
         n = len(nums)
         a = f(nums)
         nums = transfer(nums)
         choices = list(filter(lambda x:x<adder, nums))
         b = 0
         for choice in choices:
            count = 1
            temp = nums.copy()
            index = temp.index(choice)
            if temp > 1:
               temp = (temp, temp-1)
            else:
               temp.pop(index)
            l = n - 1
            for each in temp:
               count *= C(l, each)
               l -= each
            b += count
         return a + b
return f(nums)+1
优化版本：
def solve(nums):
def C(m, n):
   molecular = 1
   for i in range(m, m-n, -1):
         molecular *= i
   denominator = 1
   for i in range(n, 0, -1):
         denominator *= i
   return int(molecular/denominator)
n = len(nums)
res = 1
for i in range(2, n+1):
   temp1 = nums
   adder = temp1
   temp2 = [(i, nums.count(i)) for i in set(temp1)]
   choices = list(filter(lambda x:x<adder, temp2))
   for choice in choices:
         count = 1
         temp3 = temp2.copy()
         index = temp3.index(choice)
         if temp3 > 1:
            temp3 = (temp3, temp3-1)
         else:
            temp3.pop(index)
         l = i-1
         for each in temp3:
            count *= C(l, each)
            l -= each
         res += count
return res

TJBEST 发表于 2019-12-29 22:01:38

本帖最后由 TJBEST 于 2019-12-30 14:33 编辑

我编了一个最傻的，不过但是如果页数过多，计算机内存有限是无法运算的哈哈。可能我的算法还有优化的可能性，不过时间不是问题，是数字太大电脑算不出来（我用到了阶乘）
def fun296(arrayGiven):#可重复那就蛋疼了
def count_sort(array):
   arraysorted = sorted(set(array))#从小打到排序
   arraycount = []#数量
   for eachele in arraysorted:
         arraycount.append(arrayGiven.count(eachele))
   return (arraysorted,arraycount)

def C_mn(m,n):#计算组合数可以优化
   A = 1
   B = 1
   for i in range(1,n + 1):
         A =A * (m - i +1)
         B = B * i
   return A//B

def lessEle(last,arraysorted,arraycount):#找到并返回比他小的元素列表
   lessArray = for i in range(0,len(arraysorted)) if arraysorted<last and arraycount>0]
   return lessArray

def chgCount(ele,arraysorted,arraycount):#改变；列表计数
   index = arraysorted.index(ele)
   arraycount = arraycount- 1

def cal(arraycount,lenth):#计算
   result = 1
   for each in arraycount:
         result = result * C_mn(lenth,each)
         lenth = lenth - each
   return result

if arrayGiven == []:
   return 0
(arraysorted , arraycount)= count_sort(arrayGiven)
lenth = len(arrayGiven)
index = 0
result = 1
while index < lenth - 1:
   if index != 0:
         chgCount(arrayGiven,arraysorted,arraycount)
   else:
         pass
   lessArray = lessEle(arrayGiven,arraysorted,arraycount)
   for eachless in lessArray:
         tempcount = arraycount.copy()
         chgCount(eachless,arraysorted,tempcount)
         result = result + cal(tempcount,lenth - 1 - index)
   index = index + 1
return result

阴阳神万物主 发表于 2019-12-29 22:04:22

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

我用你这个，答案会出错呢。
>>> solve()
5
>>>
应该输出 3 呢。
11112->11121->11211->12111->21111
还能有别的排列吗？

阴阳神万物主 发表于 2019-12-29 22:05:20

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

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

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

d =
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 and x<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)
         #print('调试',each,b)
         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))

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

排列数公式：https://gss2.bdstatic.com/-fo3dSag_xI4khGkpoWK1HF6hhy/baike/pic/item/9213b07eca806538127faa2098dda144ad34826f.jpg
组合数公式：https://gss2.bdstatic.com/-fo3dSag_xI4khGkpoWK1HF6hhy/baike/pic/item/279759ee3d6d55fb34fde7ec66224f4a21a4ddc5.jpg

Unicorn# 发表于 2019-12-29 22:16:56

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

应该输出 3 呢。

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

Unicorn# 发表于 2019-12-30 01:58:51

能想出来的最好方案了
才思枯竭肝到两点
输入数组长度达到1000时超出递归深度限制，1000以内完美运行
明天再写一个列表版的，就没有深度限制了
困死了
{:10_296:}
def solve2(nums):
def transfer(nums):
   res = []
   for each in set(nums):
         res.append((each, nums.count(each)))
   return res
def C(m, n):
   molecular = 1
   for i in range(m, m-n, -1):
         molecular *= i
   denominator = 1
   for i in range(n, 0, -1):
         denominator *= i
   return int(molecular/denominator)
def f(nums):
   if len(nums) == 1:
         return 0
   else:
         adder = nums
         n = len(nums)
         a = f(nums)
         nums = transfer(nums)
         choices = list(filter(lambda x:x<adder, nums))
         b = 0
         for choice in choices:
            count = 1
            temp = nums.copy()
            index = temp.index(choice)
            if temp > 1:
               temp = (temp, temp-1)
            else:
               temp.pop(index)
            l = n - 1
            for each in temp:
               count *= C(l, each)
               l -= each
            b += count
         return a + b
return f(nums)+1

Croper 发表于 2019-12-30 13:55:24

本帖最后由 Croper 于 2019-12-30 14:06 编辑

def func296(l:list)->int:
counts=[]
ret=0
t=1
i=0
for n in reversed(l):
   p,q=0,len(counts)
   while p<q:
         r=(p+q)//2
         if counts==n:
            p=r
            counts+=1
            break
         elif counts>n:
            q=r
         else:
            p=r+1
   else:
         counts.insert(p,)

   for count_pair in counts[:p]:
         ret+=t*count_pair//counts

   i+=1
   t*=i
   t//=counts

return ret+1

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

本帖最后由 fan1993423 于 2019-12-30 14:51 编辑

from math import factorial
from collections import Counter
from copy import deepcopy
def fun295(x):
if len(x)==len(set(x)):
   length=len(x)
   if length<1:
         return 0
   x_sort=sorted(x)
   initialization=0
   for i in range(length):
         initialization+=x_sort.index(x)*factorial(length-i-1)
         x_sort.remove(x)
   return initialization+1
else:
   sort_set_x=sorted(list(set(x)))
   length=len(x)
   initialization=0
   d=deepcopy(x)
   t=1
   for i in range(length):
         index=sort_set_x.index(d)
         while index:
            k=sort_set_x.pop(0)
            k_index=x.index(k)
            x.remove(k)
            shengxia_x=dict(Counter(x)).values()
            x.insert(k_index,k)
            for j in shengxia_x:
               t*=factorial(j)
            initialization+=factorial(len(x)-1)/t
            index-=1
         x.pop(0)
         sort_set_x=sorted(list(set(x)))
return int(initialization)+1

fan1993423 发表于 2019-12-30 15:07:19

另外写个代码少点，但是可能运算量要大的多的代码
from itertools import permutations
def fun295(x):
k=sorted(list(set(permutations(x))))
return k.index(tuple(x))+1

沙里爬 发表于 2019-12-30 18:22:11

本帖最后由沙里爬于 2019-12-31 09:54 编辑

不知道满不满足条件
def Factorial(num):
s=1
for i in range(1,num+1):
   s *=i
return s
def geshu(num,lst):
lst1 = lst.copy()
lst1.remove(num)
repetition_num=1
for i in set(lst1):
   repetition_num *= Factorial(lst1.count(i))
return Factorial(len(lst1))//repetition_num
def position(num,lst):
lst1=list(set(lst))
if len(lst1)==1:
   return 1
target = lst1.index(num)
k = 0
for i in range(target):
   k += geshu(lst1,lst)
return k
def solution(lst):
k = 0
lenth=len(lst)
for i in range(lenth):
   if len(set(lst))==1:
         k+=1
         break
   else:
         k += position(lst,lst)
         del lst
print(k)

hfwei0 发表于 2019-12-30 18:58:30

本帖最后由 hfwei0 于 2019-12-31 01:03 编辑

import math,random

def fac(lst0):
a=1
for i in range(len(lst0)):
   a*=math.factorial(lst0)
return a

def pmu(lst):
sk=[]
sv=[]
lst1=lst[:]
lst1.sort()
n=0
total=0
while n < len(lst1):
   tmp=lst1.count(lst1)
   if tmp>1:
         sk.append(lst1)
         sv.append(tmp)
   n+=tmp
for i in range(len(lst)):
   temp=lst1.index(lst)
   if lst in sk:
         stmp=sk.index(lst)
         sv-=1
         if sv == 1:
            sk.pop(stmp)
            sv.pop(stmp)
   total+=temp*(math.factorial(len(lst1)-1)/fac(sv))
   lst1.pop(temp)
return int(total+1)
c=[]
for i in range(300):
c.append(random.randint(1,10))
print(pmu(c))
print(pmu(c))只能到300。。。

_2_ 发表于 2019-12-30 19:47:07

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

这个6诶

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

def justcount(list1):
import itertools
list2 = list1.copy()
list2.sort()
list3 = list(itertools.permutations(list2,len(list2)))
temp = 0
while temp < len(list3):
   if list3.count(list3) > 1:
         temp2 = list3.count(list3)
         temp3 = list3
         for i in range(temp2):
            list3.remove(temp3)
         list3.insert(temp,temp3)
   temp += 1
return list3.index(tuple(list1))+1

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

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

{:10_256:}{:10_256:}

zltzlt 发表于 2019-12-30 21:40:56

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

解答错误

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

Unicorn# 发表于 2019-12-30 21:43:44

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

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

fan1993423 发表于 2019-12-30 23:58:15

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

输入：

不好意思，刚看了下，忘了重新对t还原为1，在32行添加一句t=1{:10_256:}
from math import factorial
from collections import Counter
from copy import deepcopy
def fun295(x):
if len(x)==len(set(x)):
   length=len(x)
   if length<1:
         return 0
   x_sort=sorted(x)
   initialization=0
   for i in range(length):
         initialization+=x_sort.index(x)*factorial(length-i-1)
         x_sort.remove(x)
   return initialization+1
else:
   sort_set_x=sorted(list(set(x)))
   length=len(x)
   initialization=0
   d=deepcopy(x)
   t=1
   for i in range(length):
         index=sort_set_x.index(d)
         while index:
            k=sort_set_x.pop(0)
            k_index=x.index(k)
            x.remove(k)
            shengxia_x=dict(Counter(x)).values()
            x.insert(k_index,k)
            for j in shengxia_x:
               t*=factorial(j)
            initialization+=factorial(len(x)-1)/t
            t=1
            index-=1
         x.pop(0)
         sort_set_x=sorted(list(set(x)))
return int(initialization)+1

阴阳神万物主 发表于 2019-12-31 00:31:56

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

阴阳神万物主 发表于 2019-12-31 01:33:27

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

Unicorn# 发表于 2019-12-29 21:35
半夜两点写完递归版本，本来想睡了明天再优化，但是没写出来睡不着
第一个是递归版本，支持列 ...
我怀疑你的组合数计算有点小问题。
>>> def C(m, n):
   molecular = 1
   for i in range(m, m-n, -1):
         molecular *= i
   denominator = 1
   for i in range(n, 0, -1):
         denominator *= i
   return int(molecular/denominator)

>>> get = C(200,100)
>>> x = y = z = 1
>>> for i inrange(200,0,-1):
   x *= i


>>> for i in range(100,0,-1):
   y *= i


>>> for i in range(200-100,0,-1):
   z *= i


>>> (x//(y*z)) - get
484929433446296225432192901808955449760872
>>>https://gss2.bdstatic.com/-fo3dSag_xI4khGkpoWK1HF6hhy/baike/pic/item/279759ee3d6d55fb34fde7ec66224f4a21a4ddc5.jpg
严格按照定义公式计算的组合数比你的大好多。

页: [1] 2

鱼C论坛's Archiver

Python：每日一题 296