algorithm - 具有特定约束的长度为 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

这只是一道简单的组合数学题。结果是^NC_L * ^N-LC_U * ^N-L-UC_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 个字符中的任意一个。