具有特定约束的长度为N的密码数

Question

考虑26个字母和10个数字的集合.

编写一个函数,返回长度为N的密码数,该密码包含至少L个小写字母,至少U个大写字母和至少D个数字.

函数签名int cntPass(int N,int L,int U,int D)

我的方法:

我试图使用递归来解决它,但我认为它是错误的.我(错误的)重现如下:

f(N,L,U,D)= f(N,L-1,U,D)+ f(N,L,U-1,D)+ f(N,L,U,D-1)[有必要的基础条件,但它没有工作].

我正在寻找更好的方法或不同的逻辑来解决这个问题.

谢谢.

Answer 1

这只是一个简单的组合问题.结果是^N C _L*^NL C _U*^NLU C _D*26 ^L*26 ^U*10 ^D*62 ^{N - U - L - D},可以简化为26 ^{L + U}*10 ^D*62 ^{N - U - L - D}*N!/(U!*L!*D!*(N - L - U - D)!).

我们在N个地方为小写字符选择L个地方.然后在剩余的N - L位置中选择大写字母的U位置.并在剩余的N - L - U位置中选择D位数.其余的都有.

L小写字母各有26个选项.U大写字母也是如此.D位数各有10个选项.对于其余的(N - L - U - D),我们可以为它们中的每一个使用26 + 26 + 10个字符中的任何一个.