一旦找到解决方案，如何尽早摆脱笛卡尔积递归函数？

Question

我正在分析单词的语音组成，作为其中的一部分，我一直在使用笛卡尔积来匹配给定单词的拼写排列。一个单词中的每个声音都可以由多个拼写表示，程序会为单词中的每个声音确定正确的拼写。列表数量未知，长度未知。

我目前是用户 itertools 的 product() 在列表理解中，即强制执行，在返回值之前检查每个排列。这是Python 3中的相关部分：

from itertools import product


def cartesian_match(string, iterables):
    """Gets the phonetic spelling breakdown of a word via cartesian product.

    Args:
        string (str):     String for which a matched spelling is wanted.
        iterables (list): A list of lists of unknown number and length.
                          Each sublist contains only str elements.
                          Each sublist contains all possible spellings of a
                          phoneme.

    Returns:
        list: the first matched list of spelling units.

    Example (simplified):
      Args:
        string = "python"
        iterables = [
          'p', 'pp'],['i', 'ie', 'y', 'igh'],['th'],['or', 'ou', 'e', 'o'],[
          'nd', 'nn', 'n', 'ne']

      Returns:
        ['p', 'y', 'th', 'o', 'n']

    """
    return [x for x in product(*iterables) if "".join(x) == string][0]

对于复杂的词，笛卡尔积很大，几千万个排列。有些单词需要 15 分钟以上的时间来计算。我有数千个单词要分析，所以速度目前是个问题。

为了加快速度，我需要一个函数，它在发现值后立即 returns，而不是形成笛卡尔积并且必须运行通过每一个排列。它还允许我优化每个子列表中的元素顺序，以便更快地获得匹配的值。

我的挑战是我无法弄清楚如何使用未知数量和未知长度的列表迭代地执行此操作，而且我试图尽早突破递归函数的任何尝试都失败了。

谁能指出我正确的方向？

Answer 1

for x in in product(*iterables):
    if "".join(x) == string:
        return x

顺便说一句：你的函数不是递归的——这个问题的标题具有误导性。

一旦找到解决方案，如何尽早摆脱笛卡尔积递归函数？

How to break early from a cartesian product recursive function once a solution is found?

python

python-3.x

recursion

itertools

cartesian-product