求解一个排列组合问题

2023-11-28 09:20:34 +08:00
ziger  ziger

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

1950 次点击
所在节点   数学  数学
18 条回复
i_have_to_pee
i_have_to_pee
2023-11-28 09:26:56 +08:00
26^6-26
dyyseo
dyyseo
2023-11-28 09:29:11 +08:00
10156900
tool2d
tool2d
2023-11-28 09:30:47 +08:00
@dyyseo 一看就是暴力递归。
kphcdr
kphcdr
2023-11-28 10:10:45 +08:00
chatgpt: 285610000
文心一言:总共有 4302433444519237641338639371120181313362464693274530819581089299121177848932103525919463014410024186049242136804762844025498706102485253056693723744312089378816 种不同的 code 满足条件
clue
clue
2023-11-28 10:48:25 +08:00
26^5 种吧?把某一位当校验位,应该能保证校验位一定不同
ziger
ziger
2023-11-28 10:54:12 +08:00
@i_have_to_pee 不可能只有 26 个不符合条件的吧😂😂
ziger
ziger
2023-11-28 10:55:07 +08:00
@kphcdr 文心一言果然名不虚传
aaramsiconm1
aaramsiconm1
2023-11-28 11:18:12 +08:00
没太看懂楼主题目,是要求每两个 code 最少有两个字符不同的 code 集合有多少个,还是这样的 code 集合中最多有多少种 code ?
ziger
ziger
2023-11-28 11:20:49 +08:00
@aaramsiconm1 后者,最多有多少种 code
ziger
ziger
2023-11-28 11:25:12 +08:00
@clue 应该是,如果只要求 1 位不同,那是 26^6 种, 要求 6 位全部不同,只有 26^1 种,中间应该是符合规律的,只是没想到严格一点的证明思路
opengps
opengps
2023-11-28 11:33:19 +08:00
考虑了半天,我也是一楼的结果,26^6 标识全部,减掉 AAAAAA -ZZZZZZ 这 26 个极端不满足即可
kphcdr
kphcdr
2023-11-28 12:04:25 +08:00
@kphcdr #4
gydi
gydi
2023-11-28 13:11:33 +08:00
26 ^ 6 - 6 * 26 * 25 - 26
要减去 AAAAAB 和 AAAAAA 这两种吧
lewuyang
lewuyang
2023-11-28 14:34:52 +08:00
@clue 我觉得就是这个结果。
w16311
2023-11-28 15:50:41 +08:00
@ziger 把 code 当作一个树,正常的排列因为每个叶子( A ,B ,C...)都是不一样的可以确保每个 code 至少有一位不同。同理,把叶子结点囊括 2 个 letter 即可且保证两个 letter 完全不一样,这样的叶子结点可选元素有 26 个,最后的解为 26^4*26=26^5 。
ps:证明 2letter 完全不同的最大集合包含元素个数为 26 ,可用反证法。
NoOneNoBody
2023-11-28 15:56:20 +08:00
两位组合,四位排列
f056917
2023-11-28 16:26:22 +08:00
266 - (26 * C(5, 1) * 255) - (26 * C(5, 2) * 254) - (26 * C(5, 3) * 253) ≈ 1,535,316,000
edward1987
2023-11-29 13:35:18 +08:00
虽然我想的也是 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

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/995804

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX