set - 对字符串进行分区的所有方法

Question

我正在尝试找到一种有效的算法来获取对字符串进行分区的所有方法

例如对于给定的字符串 'abcd' =>
'a' 'bcd'
'a' 'b' 'cd'
'a' 'b' 'c' 'd'
'ab' 'cd'
'ab' 'c' 'd'
'abc' 'd'
'a'、'bc'、'd

任何语言都将受到赞赏

提前致谢!

Answer 1

问题分析

每对相邻字符之间，可以决定是否剪切。对于大小为 n 的字符串，有 n-1 个位置可以剪切或不剪切，即有两种可能性。因此，大小为 n 的字符串可以按 2^n-1 方式进行分区。

输出由 2^n-1 个分区组成，每个分区都有 n 个字符和分隔符。因此我们可以将输出大小描述为 f(n) = 2^n-1 * n + s(n) 其中 s(n) ≥ 0 考虑分区分隔符和行分隔符。

因此，仅由于输出大小，解决此问题的算法必须具有指数运行时间或更差:Ω(2ⁿ)。

(0 ≤ c * 2ⁿ = ½ * 2ⁿ = 2^n-1 ≤ 2^{n -1} * n ≤ f(n) 对于所有 n≥k 且具有正常数 c=½, k=1)

<小时/>

解决方案

我选择将分区表示为整数。 cutpoints 中的每一位决定是否在字符 i 和 i+1 之间进行剪切。要迭代所有可能的分区，我们只需遍历 0 和 2^(n-1) - 1 之间的所有整数即可。

示例:对于长度为 4 的字符串，我们遍历 0 和 2^3 - 1 或 0 和 7 或二进制:000 和 111。

# (python 2 or 3)
def all_partitions(string):
    for cutpoints in range(1 << (len(string)-1)):
        result = []
        lastcut = 0
        for i in range(len(string)-1):
            if (1<<i) & cutpoints != 0:
                result.append(string[lastcut:(i+1)])
                lastcut = i+1
        result.append(string[lastcut:])
        yield result

for partition in all_partitions("abcd"):
    print(partition)

内存使用情况:

我认为我的解决方案使用 Python 3 的 O(n) 内存。一次仅生成一个分区，它被打印出来并且不再被引用。当然，如果您保留所有结果，例如将它们存储在列表中。

在Python 2中，将range替换为xrange，否则所有可能的切点将存储在列表中，因此需要指数级的内存.

<小时/>

JavaScript解决方案

// ES6 generator
function* all_partitions(string) {
    for (var cutpoints = 0; cutpoints < (1 << (string.length - 1)); cutpoints++) {
        var result = [];
        var lastcut = 0;
        for (var i = 0; i < string.length - 1; i++) {
            if (((1 << i) & cutpoints) !== 0) {
                result.push(string.slice(lastcut, i + 1));
                lastcut = i + 1;
            }
        }
        result.push(string.slice(lastcut));
        yield result;
    }
}

for (var partition of all_partitions("abcd")) {
    console.log(partition);
}

使用 NodeJS v4.4.3 进行测试(免责声明:我之前没有使用过 NodeJS)。