string - 生成所有字符串组合的算法

Question

假设我有一个字符串列表，如下所示:

strings = ["abc", "def", "ghij"]

请注意，列表中字符串的长度可能会有所不同。

生成新字符串的方法是按顺序从列表的每个元素中取出一个字母。示例:“adg”和“bfi”，但不是“dch”，因为这些字母的顺序与它们在列表中出现的顺序不同。因此，在这种情况下，我知道列表中只有三个元素，我可以相当轻松地使用嵌套的 for 循环结构生成所有可能的组合，如下所示:

for i in strings[0].length:
   for ii in strings[1].length:
      for iii in strings[2].length:
         print(i+ii+iii)

当我事先不知道字符串列表有多长时，就会出现问题。如果列表有 n 个元素长，那么我的解决方案需要 n 个 for 循环才能成功。

有人能给我指出一个相对简单的解决方案吗？我正在考虑一种基于 DFS 的解决方案，将每个字母转换为一个节点，并在相邻字符串中的所有字母之间创建连接，但这似乎需要太多努力。

Answer 1

在 python 中，您可以使用 itertools.product

例如:

>>> for comb in itertools.product("abc", "def", "ghij"):
>>>   print(''.join(comb))
adg
adh
adi
adj
aeg
aeh
...

或者，使用解包:

>>> words = ["abc", "def", "ghij"]
>>> print('\n'.join(''.join(comb) for comb in itertools.product(*words)))
(same output)

product 使用的算法非常简单，从其源代码中可以看出(特别是查看函数 product_next)。它基本上枚举了混合基系统中所有可能的数字(其中每个数字位置的乘数是相应单词的长度)。一个仅适用于字符串并且不实现 repeat 关键字参数的简单实现可能是:

def product(words):
    if words and all(len(w) for w in words):
        indices = [0] * len(words)
        while True:
            # Change ''.join to tuple for a more accurate implementation
            yield ''.join(w[indices[i]] for i, w in enumerate(words))
            for i in range(len(indices), 0, -1):
                if indices[i - 1] == len(words[i - 1]) - 1:
                    indices[i - 1] = 0
                else:
                    indices[i - 1] += 1
                    break
            else:
                break