付费问个数组排列问题

已知：允许两个组合之间一个数字相同，5 个整数的组合，1000 个组合至少需要多少个整数？

组合 1：1，2，3，4，5

组合 2：1，6，7，8，9

组合 3：2，6，10，11，12

...

已知：允许两个组合之间一个数字相同，5 个整数的组合，1000 个组合至少需要多少个整数？组合 1：1，2，3，4，5 组合 2：1，6，7，8，9 组合 3：2，6，10，11，12 谢谢，求多少个，付费求解。

waytoexplorewhat

2021-02-09 20:02:16 +08:00

两个组合之间一个数字相同，那 1000 个组合共用 1 个整数，其他数字不同就好了。共 4001 个整数

chocovon

2021-02-09 20:45:28 +08:00

每 15 个数就可以刚好生成 6 个组合，所以只需要 1000/6=166 个这样的 15 个数生成 996 个组合，余下 4 个组合需要至少 14 个数，总共至少需要 166*15+14=2504 个数

Raven316

2021-02-09 21:36:36 +08:00

我没法用数学的方法来计算，所以我写了一个程序，然后跑了一下。

程序的思路是：
一开始只有一个元素的 list：[[1,2,3,4,5]]

接下来尝试 999 次扩张这个数组：
1 如果可以不增加所有数组的最大值的情况下，添加一个 5 整数组合，那就添加进去
2 如果在不增加最大值的情况下无法添加组合，那么遍历所有可能，取增加最大值幅度最小的可能。（在某个时间以后，增加的幅度不是 0 就是 1，我无法证明为什么，只是观察到这个现象）

注意：以上有两个原则
1 没有取所有可能，只是取了增加最大值幅度最小的可能
2 没有取所有同等条件的可能，只是任意取了一个。

因为我发现如果穷举的话，个人电脑是不可能的，而且我是用 python 写的程序。

以下稍微证明一下程序的逻辑（不严谨，但是我相信是正确的）：

明确一个概念：
首先在这个 list 中，所有数字的地位都是同等的，他们只是不同的 symbol，因为并没有数学运算，所以，你可以想象，给定 5 个数字，最多一个组合，给定 9 个数字，最多两个组合，等等，组合个数和数字个数必然是单调的递增关系，因此，我的做法相当于，先尽量利用目前已有的数字个数，得出现有的数字个数可能的最大组合数，然后增加数字的数量，幅度取最小的可能，再把多出来的数字利用完（这里可以显然看出一下子增加过多的数字是没有任何必要的，应该取增加数字个数最小的幅度，而且在程序运行的实际结果看来，在后期基本上都是一次增加一个数字）

那么为什么任取一种可能是正确的呢？
你会发现如果给定 9 个数字，有很多种可能
例如：
[1,2,3,4,5],[1,6,7,8,9]
[1,2,3,4,5],[2,6,7,8,9]
...
等等

但是它们都是“同构”的，你可以想象这些组合可能有很多种，但是具有相同的结构。

因此，给定一个数字上限，你把它可能有的所有组合全部找了出来，你就找出了唯一可能的结构，具体形式是不重要的。这是我对随便取一种可能的证明（非常不严谨，我其实也有怀疑）。

我跑的结果 167

Raven316

2021-02-09 21:41:39 +08:00

。。。太大了贴不下我的天呐。

https://pan.baidu.com/s/1fj2fqfOirMZoxnndY8UZGA

vpj7

nicevoice

2021-02-09 22:10:21 +08:00

@Raven316 烦请列一下公式。谢谢

Raven316

2021-02-09 22:11:32 +08:00

@nicevoice 没公式，每一步都是穷举出来的，有代码，写的很随意

nicevoice

2021-02-09 22:15:30 +08:00

@Raven316 1 和 130 这个组合不见了，。。。

Raven316

2021-02-09 22:21:17 +08:00

@nicevoice 啥意思

neteroster

2021-02-09 22:39:34 +08:00

我认为 #2 正确。

neteroster

2021-02-09 22:48:15 +08:00

C1 = {A1,A2,A3,A4,A5}
C2 = {A1,A6,A7,A8,A9}
C3 = {A2,A6,A10,A11,A12}
C4 = {A3,A7,A10,A13,A14}
C5 = {A4,A8,A11,A13,A15}
C6 = {A5,A9,A12,A14,A15}
---
可以发现，C7 将无法使用 A1 - A15 中的任意一个数，因为 C1 - C6 中的每一个元素均被使用两次。形成 1000 组数就需要 166 个这样的 C1 - C6，并且还需要一组 (C1 - C4 （注意 C4 的最后一个数是 14 ）)，也就是 (166*15 + 14) 个数。