给定 n 个数字和 k 个槽。这样对于每个插槽，它可以是 0 或小于前一个数字的数字，Combinatorics

Question

我有编码问题。给定 n 个数字和 k 个槽。这样对于每个插槽，它可以是 0 或小于前一个数字的数字。例如

对于 n=4,k=4

0000, 3000, 3200, 3210 etc.

对于 n=7,k=3

000, 700, 541, 731, 540 etc.

谁能告诉我这里的模式是什么，换句话说，描述可能性数量的公式是什么？

一些 python 说明问题的代码（代码本身并不重要，我正在寻找 make_encod(n,k))

的封闭形式

from math import factorial
import math

def make_encod(n,k):
    tol=[""]
    for i in range(0,k):
        tol=make_strin_from_tile(0,max(n-i,1),tol)
    print(len(tol))
    print(tol)


def make_strin_from_tile(f,t,all):
    a=[]
    for b in all:
        for i in range(f,t):
            if len(b)==0 or int(b[-1])>i or int(b[-1])==0==i:
                a.append(f"{b}{i}")
    return a
#just some examples
print(make_encod(3,1))
print(make_encod(3,2))
print(make_encod(3,3))
print(make_encod(5,4))

将输出：

> 3
['0', '1', '2']
None
4
['00', '10', '20', '21']
None
4
['000', '100', '200', '210']
None
16
['0000', '1000', '2000', '2100', '3000', '3100', '3200', '3210', '4000', '4100', '4200', '4210', '4300', '4310', '4320', '4321']
None

我正在寻找一个公式来告诉我 make_encod(n,k)) 的答案？一定有比实际经历这个更聪明的东西

Answer 1

您可以在此处使用递归函数。

def recur(lst,ln,curr='a'):
     if ln==len(curr[1:]):
         print(curr[1:])
         return
     else:
         for i in lst:
             if curr[-1]>i or i=='0':
                 recur(lst,ln,curr+i)

为什么我使用 'a' 作为初始 curr 是因为 all('a'>str(i) for i in range(10))= True.

a=[str(i) for i in range(3)] #['0','1','2']
recur(a,1)
#0 1 2
recur(a,2)
00 10 20 21
recur(a,3)
000 100 200 210
b=[str(i) for i in range(5)] #['0','1','2','3','4']
recur(b,4)
0000 1000 2000 2100 3000 3100 3200 3210 4000 4100 4200 4210 4300 4310 4320 4321

Answer 2

如果我理解正确，这个问题对应

What is the number of combinations to pick up to k elements from a set of n distinct numbers

因为您可以通过从有序集合 [n, n-1, n-2 ... 1] 中划掉除 k 或更少 之外的所有组合来获得所有合法组合，并且然后用零填充所有剩余的插槽。

一组 n 中的 k 个或更少对象的数量是

( n! / n! ) + ( n! / (n-1)! ) + ... + ( n! / (n-k)! ) 
= sum_(i=0)^k (n!)/((n - i)!)

我目前无法说出明确的公式。稍后我可能会回来尝试解决它，但欢迎任何比我更擅长解决求和问题的人这样做。

免责声明：我从来没有用英语做过数学，所以如果我的某些词汇有问题，请原谅

给定 n 个数字和 k 个槽。这样对于每个插槽，它可以是 0 或小于前一个数字的数字，Combinatorics

Given n numbers and k slots. Such that for each slot it can be either 0, or a number less than the previous number, Combinatorics

python

python-3.x

combinatorics