求解一个排列组合问题

[ziger]

code 由 6 个英文字符[A-Z]组成，如 AAAAAA ； 要求每两个 code 最少有两个字符不同， 如 AAAAAA ，AAAABB ； 一共有多少种 code ？

[i_have_to_pee]

26^6-26

[dyyseo]

10156900

[tool2d]

@dyyseo 一看就是暴力递归。

[kphcdr]

chatgpt: 285610000
文心一言：总共有 4302433444519237641338639371120181313362464693274530819581089299121177848932103525919463014410024186049242136804762844025498706102485253056693723744312089378816 种不同的 code 满足条件

[clue]

26^5 种吧？把某一位当校验位，应该能保证校验位一定不同

[ziger]

@i_have_to_pee 不可能只有 26 个不符合条件的吧😂😂

[ziger]

@kphcdr 文心一言果然名不虚传

[aaramsiconm1]

没太看懂楼主题目，是要求每两个 code 最少有两个字符不同的 code 集合有多少个，还是这样的 code 集合中最多有多少种 code ？

[ziger]

@aaramsiconm1 后者，最多有多少种 code

[ziger]

@clue 应该是，如果只要求 1 位不同，那是 26^6 种， 要求 6 位全部不同，只有 26^1 种，中间应该是符合规律的，只是没想到严格一点的证明思路

[opengps]

考虑了半天，我也是一楼的结果，26^6 标识全部，减掉 AAAAAA -ZZZZZZ 这 26 个极端不满足即可

[kphcdr]

@kphcdr #4

[gydi]

26 ^ 6 - 6 * 26 * 25 - 26
要减去 AAAAAB 和 AAAAAA 这两种吧

[lewuyang]

@clue 我觉得就是这个结果。

[w16311]

@ziger 把 code 当作一个树，正常的排列因为每个叶子（ A ，B ，C...）都是不一样的可以确保每个 code 至少有一位不同。同理，把叶子结点囊括 2 个 letter 即可且保证两个 letter 完全不一样，这样的叶子结点可选元素有 26 个，最后的解为 26^4*26=26^5 。
ps：证明 2letter 完全不同的最大集合包含元素个数为 26 ，可用反证法。

[NoOneNoBody]

两位组合，四位排列

[p8YFk4f3E8SJ3aEv]

266 - (26 * C(5, 1) * 255) - (26 * C(5, 2) * 254) - (26 * C(5, 3) * 253) ≈ 1,535,316,000

[edward1987]

虽然我想的也是 26^5 ，但是暴力求解的结果小于这个理论值。
https://jsfiddle.net/vdtn40hy/8/
在集合大小为 5 的情况下，分别跑了 长度为 3 、4 、5 、6 的 CODE 集合大小，都比 x^(n-1)小
run(3); // 19
run(4);// 89
run(5);// 421
run(6);// 2045