将“单词/部分”组合成“整体/字符串”？

Question

假设我有一个不同长度的伪单词。f、 e:a，b，r，c，brac，rac，ab，ra，bra，ca，dabr，abr

假设目前我有一个匹配字符串：abrac

我可以用不同的方式来匹配它：a:brac，a:bra:c，ab:ra:c，a:bra:c，a:b:rac，a:b:r:a:c，ab:rac

生成所有可能的排列组合“块”以生成所需的“字符串”的廉价快速方法是什么

高层的当前想法：

blocks = [ w for w in words if w in string ]
perms =  [ [ c for c in [':'.join(lst) for lst in permutations(blocks,N)] if string == c.replace(':','') ] for N in [2,3,4] ]

: [['a:brac', 'ab:rac'], ['a:b:rac', 'a:bra:c', 'ab:ra:c', 'abr:a:c'], ['a:b:ra:c', 'ab:r:a:c']]

N is unknown, plus must be 2,3,4... ? Possibly too many combinations are generated i.e. it is slow i.e. generation have to be controlled somehow !

我的最终目标是选择“块数”最少且“块数”最长的组合。 但如果你愿意，现在可以跳过这个

Answer 1

我会选择一个递归函数，在候选函数的末尾添加后缀。删减过长或前缀与字符串不匹配的候选项，使其不会失控。如果您试图首先生成所有排列，那么您会发现，这将太慢

更详细地说，递归函数采用当前前缀字符串和用于创建它的块列表。然后它尝试附加每个块，并递归地调用自己。找到匹配项后，打印使用的块

我在几行代码中实现了这一点，它会立即生成结果

为了实现使用最少块的最终目标，可以使用广度优先搜索。生成所有1块字符串。然后将所有可能的块添加到每个块中，以生成2块字符串。根据需要重复，直到得到所需的字符串。在每个步骤中，丢弃不是所需字符串前缀的字符串，这样它就不会失控