问题标签 [combinatorics]

我在工作中解决了一些分组问题。有很多问题，请多多包涵。我觉得它们很有趣。如果这里的任何人也对组合学感兴趣，请帮助我。

好的，所以我们有一堆字符，在这里我已经采取了援助。

1. 我们可以通过哪些方式对元素进行分组？假设我们有 4 个字符 aid 。有效组（保留顺序）将是：

   艾滋病 艾滋病
   艾滋病
   艾滋病
   艾滋病
   艾滋病
   艾滋病
   艾滋病
   艾滋病

您如何枚举所有组？你能告诉我任何 n 个字母有多少种组合吗？

2. 特别案例

• 如果案件有所作为，比如 Ai sd 和 ai sd 是两组呢？

• 列举所有案例需要多长时间？找到 4 个字母和 5 个字母的案例之间的时间差是多少？

• 如果你把“空格”当作一个字符。在所有的枚举之后，你会写多少个字符？

• 如果您根据距离定义从一个词到另一个词的转换。说“ai ds”和“ai ds”有 1 个距离，因为您应该将字母“i”移动一步。你能在任何单词的两边找到 n 距离的单词吗？

编辑：
“艾滋病”是一个词。
“a ids” “aid s” 是与原始单词“aids”相距 1 的两个单词。
“a id s”是一个与原始单词“aids”相距两个距离的单词。
“aid s”是一个与单词相距三个距离的单词。

这个问题似乎是金矿。

奖励：两个单词之间的最小距离是多少。就像“艾滋病”与“一个ID”的距离是一个距离，也是两个距离。是否有一个“中点”词，您可以从该词以最短的距离到达枚举中的任何其他词？从一个词到另一个词有多少条路径？

给定任何可迭代对象，例如：“ABCDEF”

将其几乎像数字系统一样对待：

A B C D E F AA AB AC AD AE AF BA BB BC .... FF AAA AAB ....

我将如何在此列表中找到第 i^个成员？有效地，而不是通过所有这些来计算。我想在这个列表中找到第 10 亿个（例如）成员。我正在尝试在 python 中执行此操作，并且我使用的是 2.4（不是选择），这可能是相关的，因为我无法访问 itertools。

很好，但不是必需的：该解决方案可以推广到伪“混合基数”系统吗？

- - 结果 - -

次：

一些背景：我正在编写一个或多或少的蛮力搜索算法来解决我遇到的问题。为了做到这一点，我需要生成和评估所有可能性，以找出最好的。由于评估实际上需要一些时间，我希望生成尽可能少的解决方案，以完全覆盖我的搜索空间。此外，我能做的元素越多越好。对于任何数字 K，通常都有 K! 排列，并且对于高于 ~10 的数字很难生成它们。

真正的问题：搜索空间应该包含两个元素的所有排列（N 次 el1 和 M 次 el2，其中 K=M+N），具有以下限制：

1. 它们必须是唯一的（即我只想要 [aabbb] 一次）
2. 我不需要任何排列的反转（即，如果我有 [aab]，我也不需要 [baa]）
3. 我认为排列是循环的，所以 [aab] = [aba] = [baa]

如果我能够做到这一点，那么可能性的数量将大大减少。由于 K 在理想情况下会很大，因此首先生成所有排列然后根据这些标准过滤它们是不可行的。我已经完成了第一个限制（见下文），它将 Matlab 的正常排列函数（perms）的数字从 2^K 减少到 K!/N!M!，这是一个巨大的胜利。第二个限制只会将可能性的数量减少一半（在最好的情况下），但我认为第三个也应该能够真正减少可能性的数量。

如果有人知道该怎么做，最好还知道如何计算有多少可能性，那将对我有很大帮助！我更喜欢解释，但代码也很好（我可以阅读类 C 语言、Java(Script)、Python、Ruby、Lisp/Scheme）。

对于有兴趣的人：这是仅获取我迄今为止拥有的唯一排列的算法：

• 如果你有 N-1 和 M 的所有排列，那么你可以通过将 e1 插入它们来使用它们来找到 N 和 M 的排列。你不能只是到处插入，因为那样你会得到重复。我不知道为什么会这样，但你可以计算出从旧的可能性中产生的新可能性的数量（我称之为“增益”）。对于第一个旧排列，这个数字从 M+1 开始，对于每个旧排列减一，直到它变为零，此时它又回到 M 等（仅当 M>=N 时才有效）。因此，如果您想计算 N=3 和 M=3 的排列，并且您有 N=2 和 M=3 的 10 个排列，它们的增益将是 [4 3 2 1 3 2 1 2 1 1]。

我被要求编写一个例程来确定产品配置器中可能组合的数量。

配置器非常简单。尽管它具有比这更多的功能，但它可以建模为几个“无线电组”（如 UI 控件），其中必须选择 n 个选项之一。

唯一可以使用的约束是规则，如果选择了一个选项，则不能选择另一个选项。

所以我想做的是计算可以配置的不同产品的数量，给定一组选项组和约束。

我采用了一种天真的方法来解决这个问题，使用包含-排除原则。但是据我所知，任何基于此方法的算法都应该在 O(2^n) 中运行，这将不起作用。当然，有几种可能的优化应该可以提供不错的运行时间，但仍然存在很容易构建的最坏情况。

这就是我现在所处的位置。有什么建议么？

更新

我意识到我还没有解释规则如何应用得足够好。

有几个组有选项。每个组中必须选择一个且只有一个选项。一个组中可以有一个或多个选项。

只有一种类型的约束。如果选择了某个组中的选项A，则无法选择其他组中的选项B。可以有任意数量的约束，没有限制有多少约束/规则适用于选项组或选项本身。

所以一个例子是：

第一组：
x1 x2 x3 x4 x5

第 2 组：
y1 y2 y3

第 3 组：
z1 z2 z3 z4

约束：
x1 <-> y2 *
x1 <-> z4
y2 <-> z2

*如果在 group1 中选择了 option x1，则不能选择 group 2 中的 option y2。

使用包含-排除，我将计算组合数为

组合 = C_无规则- C _r[1] - C _r [2] - C _r [3] + C _r [1,2] + C _r [1,3] + C _r [2,3] - C _r [1, 2,3]

在哪里

C_无规则= 5 * 3 * 4

C _r [a,b,c] = 违反规则 a、b 和 c 的组合数。

不幸的是，该方法需要 2^|rules| 计算。

假设一个游戏中一个人掷出 20 个 8 面骰子，总共有 8^20 种可能的结果。为了计算特定事件发生的概率，我们将事件发生的方式数除以 8^20。

可以计算出正确获得 5 个骰子值 3 的方法的数量。（20 选择 5）给了我们 3 的订单数量。7^15 给了我们在 15 次掷骰中无法获得 3 的方式的数量.

答案也可以看成我可以用多少种方式重新排列字符串 3,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0,0,0 ,0,0（20 选择 5）乘以我们为零的值的总数（假设 7 个合法值）7^15（这是正确的）。

• 问题 1：我如何计算获得完全相同值的 5 个骰子的方法数量（即，对于所有骰子值）。注意：如果我只是天真地使用上面的第一个答案并乘以 bt 8，我会得到大量的重复计算吗？

  我知道我可以解决每种情况 (5 1's), (5, 2's), (5, 3's), ... (5's, 8) 对它们求和（更简单地说 8*(5 1's) ）。然后减去重叠数的总和 (5 1's) 和 (5 2's), (5 1's) 和 (5 3's)... (5 1's) 和 (5, 2's) 和 ...和 ​​(5, 8's)但这似乎非常混乱。我会以一种扩展到大量样本和大量类的方式对此进行概括。

• 如何计算获得至少5 个相同值的骰子的方法数？

  所以 111110000000000000000 或 11110100000000000002 或 11111100000001110000 或 11011211222222223333，但不是 00001111222233334444 或 0630511514225。

我正在寻找解释数学或指向支持此的库（尤其是 python 模块）的答案。细节和例子的加分。

生成一个列表列表（或打印，我不介意）一个大小为 N 的帕斯卡三角形，代码行数尽可能少！

这是我的尝试（python 2.6中的 118 个字符使用技巧）：

解释：

• 列表理解的第一个元素（当长度为 0 时）是[1]
• 下一个元素通过以下方式获得：
• 取上一个列表并制作两个列表，一个在开头填充 0，另一个在末尾填充。
  • 例如，对于第二步，我们采取[1]并制作[0,1]和[1,0]
• 将两个新列表逐个元素相加
  • 例如，我们创建一个新列表[(0,1),(1,0)]并使用 sum 进行映射。
• 重复n次，仅此而已。

用法（漂亮的印刷，实际上是在代码高尔夫 xD 之外）：

输出：

如果每个单词都以随机辅音开头，然后元音和辅音交替出现，我可以从英文小写字母中生成多少个长度为 6 的单词？

如果我在字母表中添加数字怎么办？

另请参阅此问题。

我有一个朋友需要计算以下内容：

在完整的图 Kn (k<=13) 中，有 k*(k-1)/2 条边。每条边可以以​​ 2 种方式定向，因此有 2^[(k*(k-1))/2] 种不同的情况。

她需要计算P[A !-> B && C !-> D] - P[A !-> B]*P[C !-> D]

X !-> Y 表示“没有从 X 到 Y 的路径”，而 P[ ] 是概率。

所以蛮力算法是检查每一个 2^[(k*(k-1))/2] 个不同的图，因为它们是完整的，在每个图中只需要考虑一组 A，B， C,D 因为对称。

然后将 P[A !-> B] 计算为“节点 1 和 2 之间没有路径的图的数量”除以图的总数，即 2^[(k*(k-1))/2]。

蛮力方法适用于数学到 K8，但她需要 K9，K10... 到 K13。

我们显然不需要在案例中找到最短路径，只想找到是否有一条。

有人有优化建议吗？（这听起来像是典型的 Project Euler 问题）。

例子：

最小图 K4 有 4 个顶点，给出 6 条边。因此，如果我们标记 4 个顶点 A、B、C 和 D，则有 2^6 = 64 种可能的方式来为边分配方向。

在某些图表中，没有从 A 到 B 的路径（比如说其中的 X），而在其他一些图中，没有从 C 到 D 的路径（假设是 Y）。但是在某些图中，没有从 A 到 B 的路径，同时也没有从 C 到 D 的路径。这些是 W。

所以和。P[A !-> B]=X/64_P[C !-> D]=Y/64P[A !-> B && C !-> D] = W/64

更新：

• A、B、C 和 D 是 4 个不同的谓词，因此我们至少需要 K4。
• 请注意，我们正在处理有向图，因此使用 UT 矩阵的正常表示是不够的。
• 在mathematica中有一个函数可以找到有向图中节点之间的距离，（如果它返回无穷大，则没有路径），但这有点矫枉过正，因为我们不需要距离，只要有路径或不是。

我知道如果我有以下一组数字

我可以有 5040 个不同的 4 位数字，使用 10！/ (10 - 4)！

但是如果我在初始组中重复一个数字，比如

我们可以建立多少个不同的 4 位数字？我知道答案是3360，只是不知道如何实现。

重要提示：在这种情况下，像“1123”或“1213”这样的数字应该是有效的组合，但不是“1113”，因为初始组中只有两个数字。

另外，对于组

应该有 2190 个 4 位数字。关于如何计算这些答案的任何想法？

这不是家庭作业，我将从特定硬件中获取这些数字，并根据组合的数量返回一些数据。

我有一个关于组合学的问题。不幸的是，我无法抽象地描述它，所以我试图将它解释为一个故事。:)

问题：

1. 校园里有100个孩子。
2. 假设值为 100-199 厘米，它们都有独特的高度。
3. 你想建立 10 个小组，每个小组由 1-99 个孩子组成。
4. 当孩子们必须按身高排序时，你怎么能建立所有的组？
5. 我需要为这些群体提供所有可能的解决方案，因为找到一个星座并不难。

简短易懂：

所有100个孩子并排站立。您只需要决定在哪里将它们分成组并为此找到所有解决方案。

示例（值是高度）：

[120 ... 190 ... 199] ... [126 ... 137 ... 144 ... 188]是不可能的

[101] ... [104 ... 105 ... 112 ... 149] ... [169 ... 189]是可能的

我希望你能帮助我。非常感谢您！

PS：这不是家庭作业。;) 通常，我需要一个函数来处理数字。但是我不能像“在对所有数字进行排序的同时构建 k 组数字”那样抽象地描述这一点。我以为你不会这样理解。:) PHP 的解决方案是最好的，但我也很高兴看到其他语言的解决方案。:)