python字符串子集的所有组合

Question

我需要字符串子集的所有组合。此外，长度为 1 的子集后面只能跟着长度 > 1 的子集。例如对于字符串 4824，结果应该是:

 [ [4, 824], [4, 82, 4], [48, 24], [482, 4], [4824] ]

到目前为止，我设法检索了所有可能的子集:

    length = len(number)
    ss = []
    for i in xrange(length):
        for j in xrange(i,length):
            ss.append(number[i:j + 1])

这给了我:

  ['4', '48', '482', '4824', '8', '82', '824', '2', '24', '4']

但我现在不知道如何将它们结合起来。

Answer 1

首先，编写一个生成所有字符串分区的函数:

def partitions(s):
    if s:
        for i in range(1, len(s) + 1):
            for p in partitions(s[i:]):
                yield [s[:i]] + p
    else:
        yield []

这会迭代所有可能的第一段(一个字符、两个字符等)，并将它们与字符串相应剩余部分的所有分区组合起来。

>>> list(partitions("4824"))
[['4', '8', '2', '4'], ['4', '8', '24'], ['4', '82', '4'], ['4', '824'], ['48', '2', '4'], ['48', '24'], ['482', '4'], ['4824']]

现在，您可以只过滤符合条件的那些，即没有两个连续长度为 1 的子串的那些。

>>> [p for p in partitions("4824") if not any(len(x) == len(y) == 1 for x, y in zip(p, p[1:]))]
[['4', '82', '4'], ['4', '824'], ['48', '24'], ['482', '4'], ['4824']]

在这里，zip(p, p[1:]) 是迭代所有连续项目对的常用方法。

---

更新:实际上，将您的约束直接合并到 partition 函数中也不是那么难。只需跟踪最后一段并相应地设置最小长度。

def partitions(s, minLength=1):
    if len(s) >= minLength:
        for i in range(minLength, len(s) + 1):
            for p in partitions(s[i:], 1 if i > 1 else 2):
                yield [s[:i]] + p
    elif not s:
        yield []

演示:

>>> print list(partitions("4824"))
[['4', '82', '4'], ['4', '824'], ['48', '24'], ['482', '4'], ['4824']]