确定可能组合的数量

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

这个问题可以分成两个简单的小问题：

1. 计算每对大括号中有多少组合，并且这些组合是用竖线分隔的
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 来处理这种情况，那也可以，替代最后三行代码，我想;-）。

Answer 2

好吧，你第一个例子里有 3 x 2 x 3 = 18 种组合。

你的第二个例子是 3 x 4 x 2 x 3 = 72 种组合。

不过，我不太明白你说的 {a|b}|{c|d} 是什么意思，我猜你的意思是从 (a 或 b) 或 (c 或 d) 中选一个，这样就有 4 种选择。

你可以在 这里 或 这里 了解一下组合的相关知识。

---

更新：没错，就是这么简单。你的问题就像是在计算一个数字中数字组合的数量。例如，如果我想找出一个 ATM 密码（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 种可能性。

你的例子用的是单词的集合，而不是数字的集合，但原理是一样的。组合的数量就是第一个集合中的项目数量 × 第二个集合中的项目数量 × ... × 第 n 个集合中的项目数量，依此类推。

当你开始添加限制条件，或者从同一个集合中选择多个项目时，事情就会变得复杂一些。