付费问个数组排列问题

• 資深大佬 : waytoexplorewhat

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

• 資深大佬 : chocovon

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

• 資深大佬 : Raven316

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

  程序的思路是：
  一开始只有一个元素的 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

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

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

  vpj7

• 主 資深大佬 : nicevoice

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

• 資深大佬 : Raven316

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

• 主 資深大佬 : nicevoice

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

• 資深大佬 : Raven316

  @nicevoice 啥意思

• 資深大佬 : neteroster

  我认为 #2 正确。

• 資深大佬 : neteroster

  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) 个数。

• 資深大佬 : XiaoxiaoPu

  @neteroster 有问题的。C7 不能使用 A1-A15，不代表后面的集合不能用。

• 資深大佬 : Raven316

  @neteroster 兄弟你写答案之前看看我 python 跑出来的答案呗，我觉得 167 就够了

• 資深大佬 : neteroster

  @XiaoxiaoPu @Raven316 确实应该是我理解错了，我之前想成：不允许一个数字同时出现在两组以上了，仔细想想主应该不是这个意思。

• 資深大佬 : BiteTheDust

  n 个数能构成的 5 元组数量似乎与 The Kruskal-Macaulay function K_5(n)很相似？
  oeis.org/A123574