Python连接字符串以生成字符串中所有单词的组合

Question

如果我的字符串是这样的：'this is a string'，我该如何通过连接每个词与其相邻的词来生成所有可能的组合？

输出结果如下：

this is a string
thisis a string
thisisa string
thisisastring
thisis astring
this isa string
this isastring
this is astring

我的尝试：

s = 'this is a string'.split()    
for i, l in enumerate(s):
        ''.join(s[0:i])+' '.join(s[i:])

这将产生以下结果：

'this is a string'
'thisis a string'
'thisisa string'
'thisisastring'

我意识到需要更改s[0:i]部分，因为它在0处被静态锚定，但我不知道如何移动到下一个单词is，同时仍然包括this在输出中。

- Jarad

Answer 1

使用itertools product的更简单方法（比被接受的答案快3倍）：

s = 'this is a string'
s2 = s.replace('%', '%%').replace(' ', '%s')
for i in itertools.product((' ', ''), repeat=s.count(' ')):
    print(s2 % i)

- panda-34

---

非常棒！我给它投了票。不过我不明白这部分代码是什么意思：“.replace('%', '%%')”。对我来说，它似乎是多余的。 - tommy.carstensen

@tommy.carstensen - 如果原始字符串中包含百分号字符，则需要转义以准备进行进一步的格式化操作。 - panda-34

Answer 2

哎呀，这比我预想的更难一些...这实际上比我想象中的要棘手 :)

主要思想：

当您拆分字符串时，空格数是拆分数组的长度减1。 在我们的示例中有3个空格:

'this is a string'
     ^  ^ ^

我们将使用二进制表示法来表示所有选项，有或没有这两个空格中的任意一个，因此在我们的情况下，它将是：

000
001
011
100
101
...

对于每个选项，我们将分别生成句子，其中111表示所有3个空格：“this is a string”，而000则表示没有空格：“thisisastring”。

def binaries(n):
    res = []
    for x in range(n ** 2 - 1):
        tmp = bin(x)
        res.append(tmp.replace('0b', '').zfill(n))
    return res


def generate(arr, bins):
    res = []
    for bin in bins:
        tmp = arr[0]
        i = 1
        for digit in list(bin):
            if digit == '1':
                tmp = tmp + " " + arr[i]
            else:
                tmp = tmp + arr[i]
            i += 1
        res.append(tmp)
    return res


def combinations(string):
    s = string.split(' ')
    bins = binaries(len(s) - 1)
    res = generate(s, bins)
    return res


print combinations('this is a string')
# ['thisisastring', 'thisisa string', 'thisis astring', 'thisis a string', 'this isastring', 'this isa string', 'this is astring', 'this is a string']

更新：
我现在看到Amadan想到了相同的想法 - 为你更快地思考而喝彩！伟大的思想是相似的 ;)

- Nir Alfasi

Answer 3

你也可以使用itertools.product()：

import itertools

s = 'this is a string'

words = s.split()
for t in itertools.product(range(len('01')), repeat=len(words)-1):
    print(''.join([words[i]+t[i]*' ' for i in range(len(t))])+words[-1])

- tommy.carstensen

---

请查看@panda-34提供的更快解决方案。 - tommy.carstensen

Answer 4

最简单的方法是递归实现。

• 终止条件：一个元素列表的Schrödinger连接为该单词。
• 循环条件：假设L是除第一个单词外所有单词的Schrödinger连接。那么列表的Schrödinger连接由L中所有元素与第一个单词直接附加组成，以及L中所有元素与第一个单词以介入空格附加组成。

(如果你无意中错过了thisis astring。如果是故意的，我肯定不知道问题是什么:P)

另一种非递归的方法是枚举从0到2^(单词数-1)-1的所有数字，然后使用每个数字的二进制表示作为选择器，判断是否需要存在空格。例如，上述的thisis astring对应于0b010，表示“nospace，space，nospace”。

- Amadan

---

你说得对，我确实漏掉了 thisis astring。谢谢你指出来。我已经在我的问题中更新了这个更正。我会花些时间消化并应用你的评论，Amadan。 - Jarad