确定可能组合的数量

Question

我试图找出有多少种可能的方法来组合该字符串中的各种元素。

"{Hello|Hi|Hey} {world|earth}{!|.|?}"

其中从每个组 ({}) 中随机选择一项（由竖线/| 分隔）并组合成单个字符串。

所以上面的“模板”可以产生：

Hello world.
Hi earth?
Hey world.
Hi world?

我猜这是一种排列，但我想确保我得到了正确的结果。

如果这也适用于“n”个嵌套项目，那就太好了。

"{{Hello|Hi|Hey} {world|earth}|{Goodbye|farewell} {noobs|n3wbz|n00blets}}"

如果可能的话，我更喜欢基于数学/统计的解决方案而不是暴力循环来获得答案。

谢谢！

Answer 1

嗯，第一个示例中有 3 x 2 x 3 = 18 种组合。

第二个示例是 3 x 4 x 2 x 3 = 72 种组合。

我不完全确定 {a|b}|{c|d} 你的意思，我假设你的意思是选择（a或b）或（c或d）之一），有4个选择。

您可能想在此处或此处。

---

更新：是的，就是这么简单。你的问题就像计算一个数字中数字组合的数量一样。例如，如果我想查找 ATM PIN 码（4 位十进制数字）的组合数，我有集合 {0-9}、{0-9}、{0-9}、{0-9}。第一选择有 10 种可能性 (= 10)。对于每个数字，第二个选择有 10 种可能性 (= 10 × 10)。对于其中每一个，第三个有 10 个 (= 10 × 10 × 10)，第四个有 10 个 (= 10 × 10 × 10 × 10 = 10,000)。直观上应该很清楚，4 位十进制数有 10,000 种可能性。

您的示例使用单词集而不是数字集，但原理是相同的。组合数是集合 1 中的项目数 × 集合 2 中的项目数 × ... × 集合 n 中的项目数等。

当您开始添加限制或从中选择多个项目时，情况会变得更加复杂同一套等

Answer 2

这个问题分解为两个简单的子问题：

1. 计算大括号内有多少个组合并在 vbar 内分隔，对于每个大括号
2. 对乘以这些数字

所以对于 1 我会使用一个简单的正则表达式 +循环方法：

import re

def docount(thestring):
    x = re.compile(r'{([^}]}')
    counts = [mo.group(0).count('|')+1 for mo in x.finditer(thestring)]
    result = 1
    for c in counts: result *= c
    return result

我也嵌入了 2 ，因为无论如何这是最微不足道的部分（如果你热衷于使用 reduce 来实现这样的目的，那也可以代替我猜最后三行；-)。