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

zltzlt

今天的题目：

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

示例 1：

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

示例 2：

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

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

TJBEST

2019-12-29 22:01:38

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

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 = [arraysorted[i] for i in range(0,len(arraysorted)) if arraysorted[i]<last and arraycount[i]>0]
        return lessArray
        
    def chgCount(ele,arraysorted,arraycount):#改变；列表计数
        index = arraysorted.index(ele)
        arraycount[index] = arraycount[index]  - 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[index - 1],arraysorted,arraycount)
        else:
            pass
        lessArray = lessEle(arrayGiven[index],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

跳转到最佳答案楼层

Unicorn#

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

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[0]
            n = len(nums)
            a = f(nums[1:])
            nums = transfer(nums)
            choices = list(filter(lambda x:x[0]<adder, nums))
            b = 0
            for choice in choices:
                count = 1
                temp = nums.copy()
                index = temp.index(choice)
                if temp[index][1] > 1:
                    temp[index] = (temp[index][0], temp[index][1]-1)
                else:
                    temp.pop(index)
                l = n - 1
                for each in temp:
                    count *= C(l, each[1])
                    l -= each[1]
                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[n-i:]
        adder = temp1[0]
        temp2 = [(i, nums.count(i)) for i in set(temp1)]
        choices = list(filter(lambda x:x[0]<adder, temp2))
        for choice in choices:
            count = 1
            temp3 = temp2.copy()
            index = temp3.index(choice)
            if temp3[index][1] > 1:
                temp3[index] = (temp3[index][0], temp3[index][1]-1)
            else:
                temp3.pop(index)
            l = i-1
            for each in temp3:
                count *= C(l, each[1])
                l -= each[1]
            res += count
    return res

TJBEST

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

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 = [arraysorted[i] for i in range(0,len(arraysorted)) if arraysorted[i]<last and arraycount[i]>0]
        return lessArray
        
    def chgCount(ele,arraysorted,arraycount):#改变；列表计数
        index = arraysorted.index(ele)
        arraycount[index] = arraycount[index]  - 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[index - 1],arraysorted,arraycount)
        else:
            pass
        lessArray = lessEle(arrayGiven[index],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

阴阳神万物主

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

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

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

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

阴阳神万物主

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

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 = [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 [x for x in b if b[x] and x<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)
            #print('调试',each,b)
            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))

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

排列数公式：

                               
登录/注册后可看大图

组合数公式：

                               
登录/注册后可看大图

Unicorn#

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

应该输出 3 呢。

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

Unicorn#

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

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[0]
            n = len(nums)
            a = f(nums[1:])
            nums = transfer(nums)
            choices = list(filter(lambda x:x[0]<adder, nums))
            b = 0
            for choice in choices:
                count = 1
                temp = nums.copy()
                index = temp.index(choice)
                if temp[index][1] > 1:
                    temp[index] = (temp[index][0], temp[index][1]-1)
                else:
                    temp.pop(index)
                l = n - 1
                for each in temp:
                    count *= C(l, each[1])
                    l -= each[1]
                b += count
            return a + b
    return f(nums)+1

Croper

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[r][0]==n:
                p=r
                counts[r][1]+=1
                break
            elif counts[r][0]>n:
                q=r
            else:
                p=r+1
        else:
            counts.insert(p,[n,1])


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

        i+=1
        t*=i
        t//=counts[p][1]

    return ret+1

fan1993423

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[i])*factorial(length-i-1)
            x_sort.remove(x[i])
        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[i])
            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

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

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

沙里爬

不知道满不满足条件

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[i],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[0],lst)
            del lst[0]
    print(k)

hfwei0

import math,random

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

def pmu(lst):
    sk=[]
    sv=[]
    lst1=lst[:]
    lst1.sort()
    n=0
    total=0
    while n < len(lst1):
        tmp=lst1.count(lst1[n])
        if tmp>1:
            sk.append(lst1[n])
            sv.append(tmp)
        n+=tmp
    for i in range(len(lst)):
        temp=lst1.index(lst[i])
        if lst[i] in sk:
            stmp=sk.index(lst[i])
            sv[stmp]-=1
            if sv[stmp] == 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))[/code]只能到300。。。

_2_

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

这个6诶

danteer

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[temp]) > 1:
            temp2 = list3.count(list3[temp])
            temp3 = list3[temp]
            for i in range(temp2):
                list3.remove(temp3)
            list3.insert(temp,temp3)
        temp += 1
    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

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[i])*factorial(length-i-1)
            x_sort.remove(x[i])
        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[i])
            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

阴阳神万物主

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

阴阳神万物主

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 in  range(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
>>>  

                               
登录/注册后可看大图

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