蛮力排列

Question

我读了下面这篇文章，不明白第四段背后的逻辑

给你N盏灯和4个开关。第一个开关切换所有的灯，第二个开关是偶数灯，第三个开关是奇数灯，最后一个开关是灯1，4，7，10，……。

给定灯的数目、N、按下按钮的次数(最多10,000)，以及一些灯的状态(例如，灯7关机)，输出灯可能处于的所有可能状态。

天真地，对于每个按钮，您必须尝试4种可能性，总共4^10000 (约10^6020 )，这意味着您无法完成搜索(这个特定的算法将利用递归)。

注意到按下按钮的顺序并不重要，这个数字会降到大约10000^4 (约10^16 )，仍然太大，无法完全搜索(但肯定比10^6000更接近)。

然而，按两次按钮和不按一次按钮是一样的，所以您真正需要检查的就是按每个按钮0次或1次。这仅仅是2^4 = 16种可能性，一定有一些迭代在时限内是可解的。

当顺序不重要时，总配置的数目是10000^4？

Answer 1

提交人规定，按按钮的次数不得超过10,000：

按下按钮的次数(最多10,000)

如果你知道按下按钮的顺序并不重要，但没有别的，那么重要的是每个按钮被按了多少次。每个按钮有10,000种可能性，所以总体上大约是10000^4。(当然，实数要小一点，因为你不能，例如，按下所有四个按钮10,000次。)