分割字符串的所有方法

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)对于所有具有正常数c=½, k=1 的n?k )

解决方案

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

示例：对于长度为 4 的字符串，我们遍历所有介于0and2^3 - 1或0and之间的整数，7以二进制表示：000and 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)

内存使用情况：

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

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

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）。