python - 按顺序生成所有可能的子串

Question

我正在寻找一个库或一种有效的方法来在 Python 中实现以下内容

Input: 
"He was hungry"

Desired Output:
[["He","was","hungry"]
["He was","hungry"]
["He","was hungry"]
["He was hungry"]]

Answer 1

这是一种递归方法:对于包含 N 个单词的输入，计算前 N-1 个单词的可能连接，然后选择是将最后一个单词作为其自己的元素附加还是将其与最右边的元素连接。

def iter_joinings(items):
    if len(items) == 0:
        return
    elif len(items) == 1:
        yield items
    else:
        right = items[-1]
        for left_a in iter_joinings(items[:-1]):
            left_b = left_a.copy()
            left_a.append(right)
            yield left_a
            left_b[-1] = left_b[-1] + " " + right
            yield left_b

s = "He was hungry"
for result in iter_joinings(s.split()):
    print(result)

结果:

['He', 'was', 'hungry']
['He', 'was hungry']
['He was', 'hungry']
['He was hungry']

---

这是一个迭代版本，以防万一您有 999 个元素的输入并且不想达到 Python 的最大递归深度:

import itertools

def iter_joinings(items):
    for decisions in itertools.product((False, True), repeat=len(items)-1):
        result = [items[0]]
        for idx, should_append in enumerate(decisions, 1):
            if should_append:
                result.append(items[idx])
            else:
                result[-1] = result[-1] + " " + items[idx]
        yield result

s = "He was hungry"
for result in iter_joinings(s.split()):
    print(result)

...尽管如此庞大的输入在任何一种情况下都需要大约 10^300 字节码指令来执行，所以这不太可能成为实际问题。