对于任何 Linux Distro 的打包系统，找出可同时安装的包的最大数量
For any Linux Distro's packaging system, find the maximum number of simultaneously installable packages
一些软件包冲突，所以不可能一次安装所有可用的软件包。给定系统的可安装软件包的最大可能数量是多少？蛮力试错法是：
- 列出每个可能的包名称，即
dglob -a > list
- 由此，为每个可能的包 combination. On my system
dglob -a | wc -l returns 91327, which would require an unfeasibly large number (1.467×10^27492) of files 创建子列表 slist1 slist2 slist3 ...。
- 运行
apt-get install 在每个列表上，rm 产生冲突。
- 按行数对剩余列表进行排序，并显示最长的一个。
wc -l slist* | head -n -1 | sort -g | tail -1.
简单，但是太费资源了，也许有更可行的方法。
随之而来的是各种相关问题，例如：
给定一个包'foo'，如何找到与[不冲突的最大可安装包数=75=]?
对于所有可能的包，哪个具有最小的最大值，（使它成为最 "quarrelsome" 的包）？
(注意：该问题适用于 Debian、Red Hat 和任何发行版或 OS 具有映射包冲突的打包系统。任何适用平台的答案都是有效的。 )
背景：
Debian 有数以万计的软件包。 dglob（来自 debian-goodies 软件包）可以方便地进行快速计数：
# show how many packages installed and available on the current system
echo $(dglob | wc -l) packages installed of \
$(dglob -a | wc -l) packages.
示例输出，（这两个数字可能会在更新和升级后定期波动，并且会因系统而异）：
5107 packages installed of 91327 packages.
数字5107当然不是最大值，但必须有最大值。
在这种情况下，暴力破解选项是唯一的选项。这里 a paper 将深入描述原因，但问题是软件包安装和 dependency/conflict 解析是一个 NP-Complete 问题。
如果每个 TRUE 答案都有一个易于检查的多项式大小的解释，则 NP 中就有问题。在这种情况下，这可以通过列出已安装的软件包和可用的软件包来完成。
如果问题的有效解决方案可以适用于 NP 中所有其他问题的有效解决方案，则 Debian 软件包安装属于 NP-hard。我将参考上面列出的论文，因为在这里证明它有点复杂，但它可以编码为 3-SAT.
由于Debian包安装是NP和NP-hard，因此是NP-complete。
以下是 APT 中的 default 求解器试图避免 NP 完全性的一些方法：
- 启发式的使用
- 对 or-group 中第一个元素的偏好
- 严格的包版本约定
- 遇到大冲突就放弃
基本上，对于像 HORN-SAT
这样的 NP 完全问题，必须专门设计约束以使问题落入已知的易处理 classes
不幸的是 find the maximum possible number of installable packages for a given system 几乎排除了我所知道的所有已知的易于处理的 classes。
所以蛮力是唯一的选项并且是一个昂贵的选项，直到发现合适的易处理class或者如果有人证明P=NP。
一些软件包冲突，所以不可能一次安装所有可用的软件包。给定系统的可安装软件包的最大可能数量是多少？蛮力试错法是：
- 列出每个可能的包名称，即
dglob -a > list - 由此，为每个可能的包 combination. On my system
dglob -a | wc -lreturns 91327, which would require an unfeasibly large number (1.467×10^27492) of files 创建子列表slist1 slist2 slist3 ...。 - 运行
apt-get install在每个列表上，rm产生冲突。 - 按行数对剩余列表进行排序，并显示最长的一个。
wc -l slist* | head -n -1 | sort -g | tail -1.
简单，但是太费资源了，也许有更可行的方法。
随之而来的是各种相关问题，例如：
给定一个包'foo'，如何找到与[不冲突的最大可安装包数=75=]?
对于所有可能的包，哪个具有最小的最大值，（使它成为最 "quarrelsome" 的包）？
(注意：该问题适用于 Debian、Red Hat 和任何发行版或 OS 具有映射包冲突的打包系统。任何适用平台的答案都是有效的。 )
背景：
Debian 有数以万计的软件包。 dglob（来自 debian-goodies 软件包）可以方便地进行快速计数：
# show how many packages installed and available on the current system
echo $(dglob | wc -l) packages installed of \
$(dglob -a | wc -l) packages.
示例输出，（这两个数字可能会在更新和升级后定期波动，并且会因系统而异）：
5107 packages installed of 91327 packages.
数字5107当然不是最大值，但必须有最大值。
在这种情况下，暴力破解选项是唯一的选项。这里 a paper 将深入描述原因，但问题是软件包安装和 dependency/conflict 解析是一个 NP-Complete 问题。
如果每个 TRUE 答案都有一个易于检查的多项式大小的解释，则 NP 中就有问题。在这种情况下，这可以通过列出已安装的软件包和可用的软件包来完成。
如果问题的有效解决方案可以适用于 NP 中所有其他问题的有效解决方案，则 Debian 软件包安装属于 NP-hard。我将参考上面列出的论文，因为在这里证明它有点复杂，但它可以编码为 3-SAT.
由于Debian包安装是NP和NP-hard，因此是NP-complete。
以下是 APT 中的 default 求解器试图避免 NP 完全性的一些方法：
- 启发式的使用
- 对 or-group 中第一个元素的偏好
- 严格的包版本约定
- 遇到大冲突就放弃
基本上，对于像 HORN-SAT
这样的 NP 完全问题，必须专门设计约束以使问题落入已知的易处理 classes不幸的是 find the maximum possible number of installable packages for a given system 几乎排除了我所知道的所有已知的易于处理的 classes。
所以蛮力是唯一的选项并且是一个昂贵的选项，直到发现合适的易处理class或者如果有人证明P=NP。