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

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

Answer 2

从您的解决方案看来，您需要有与字符串一样多的

for

循环。对于最终字符串中生成的每个字符，您需要一个

for

循环来遍历可能的字符列表。为此，您可以制定递归解决方案。每次递归深入一层时，您只需运行一个

for

循环。有多少个字符串就有多少级递归。

这是一个Python示例：

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

def rec(generated, k):
    if k==len(strings):
        print(generated)
        return

    for c in strings[k]:
        rec(generated + c, k+1)

rec("", 0)

Answer 3

这是我在 Javascript 中的做法（我假设每个字符串不包含重复字符）：

function getPermutations(arr)
{
  return getPermutationsHelper(arr, 0, "");
}

function getPermutationsHelper(arr, idx, prefix)
{
  var foundInCurrent = [];
  for(var i = 0; i < arr[idx].length; i++)
  {
    var str = prefix + arr[idx].charAt(i);

    if(idx < arr.length - 1)
    {
      foundInCurrent = foundInCurrent.concat(getPermutationsHelper(arr, idx + 1, str));
    }
    else
    {
      foundInCurrent.push(str);
    }
  }
  return foundInCurrent;
}

基本上，我使用的是递归方法。我的基本情况是当我的数组中没有更多单词时，在这种情况下，我只需将

prefix + c

添加到我的数组中，为我最后一个单词中的每个

c

（字符）。

否则，我会尝试当前单词中的每个字母，并将我构建的前缀递归地传递到下一个单词。

对于您的示例数组，我得到：

adg adh adi adj aeg aeh aei aej afg afh afi afj bdg bdh bdi 
bdj beg beh bei bej bfg bfh bfi bfj cdg cdh cdi cdj ceg ceh 
cei cej cfg cfh cfi cfj

Answer 4

需要零递归或循环：

---

    abc def ghij

---

|adg|adh|adi|adj|aeg|aeh|aei|aej|afg|afh|afi|afj
|bdg|bdh|bdi|bdj|beg|beh|bei|bej|bfg|bfh|bfi|bfj
|cdg|cdh|cdi|cdj|ceg|ceh|cei|cej|cfg|cfh|cfi|cfj

---

# gawk profile, created Thu Oct 26 09:05:13 2023

 1  {   print

 1        __ = $++_
 1       ___ = $++_
 1      ____ = $++_

 1      gsub(_ = ".", _____ = "\\&&", ___) + gsub(_, _____,
                ____)  +  gsub(_, ___, __) + gsub(_ = _ ".",
                                 ____, __) + gsub(_ ".", "|&", __)
 1      print __
    }'