1

我试图弄清楚有多少种可能的方法可以组合这个字符串中的各种元素。

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

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

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

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

我猜这是一种排列，但我想确保我做对了。

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

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

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

谢谢！

4

2 回答 2

6

好吧，在您的第一个示例中有 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 中的项目数，等等。

当您开始设置限制或从同一组中选择多个项目等时，它会变得更加复杂。

于 2010-01-04T05:17:29.733 回答
0

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

  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用于此类目的，那也可以代替最后三行，我猜；-)。

于 2010-01-04T05:38:30.503 回答