java递归方法生成字符串的所有分区

Question

我试图用String的partitioning来解决这个问题。让我们以“abc”为例
有4个partitions-{a,bc}, {ab,c}, {abc}, {a,b,c}.
我正试图编写一个recursive方法来生成partitions到ArrayList{}的ArrayList，但我很难做到这一点。非常感谢您的帮助

static List<List<String>> partitions = new ArrayList<>();
static List<String> partition = new ArrayList<>();

static void recurse(int size, String str) {
    if (str.length() <= size) {
        return;
    }
    partition.add(str.substring(0, size));
    for (int i = 1; i < str.length(); i++) {
        if (size < str.length())
            recurse(i, str.substring(size));
    }
    partitions.add(partition);
}

现在当我调用这个方法时，它会输出

[[, a, b, ab], [, a, b, ab], [, a, b, ab], [, a, b, ab]]

而不是[[a, b, c], [a, bc], [ab, c], [abc]]

，所以我肯定做错了什么：

recurse(0, "abc");
    System.out.println(partitions.toString());

Answer 1

我认为使用全局变量不是个好主意

递归函数可以返回分区列表

所以，考虑函数的输入和输出

示例：

"ABC"

func("ABC") => func("BC") => func("C")

func("C") returns [["C"]]

因此，您可以在“C”前面附加“B”，或者创建一个分区

func("BC") returns [["BC"], ["B", "C"]]

然后用“A”

func("ABC") returns [["ABC"], ["A", "BC"], ["AB", "C"], ["ABC"]]

代码：

static List<List<String>> recursive(String str) {
    List<List<String>> result = new ArrayList<>();

    if (str.length() == 1) {
        result.add(new ArrayList<>());
        result.get(0).add(str);
        return result;
    }

    for (List<String> list : recursive(str.substring(1))) {
        List<String> append = new ArrayList<>(list);
        append.set(0, str.substring(0, 1) + append.get(0));
        List<String> add = new ArrayList<>(list);
        add.add(0, str.substring(0, 1));
        result.add(append);
        result.add(add);
    }
    return result;
}

添加：

此外，您的代码只创建一次partition。所以partitions中的partition来自同一个引用

因此，添加或编辑partition会影响每一个partition

如你所见，所有的partition都是一样的

由于这些原因，您最好在每个步骤中创建新的ArrayList，而不是使用全局变量

Answer 2

另一种选择是，如果您更喜欢使用Java 8流，而不是传统的迭代：

private Stream<List<String>> partitions(String text) {
    if (text.isEmpty())
        return Stream.of(new ArrayList<>());
    else
        return IntStream.rangeClosed(1, text.length()).boxed()
            .flatMap(i -> partitions(text.substring(i))
                .peek(p -> p.add(0, text.substring(0, i))));
}

例如，partitions("abcde").forEach(System.out::println)将打印字符串的所有分区

如果要转换回列表，则：

List<List<String>> partitions = partitions(text).collect(Collectors.toList());

如果您不熟悉streams，else子句可以解释为：对于介于1和字符串长度（包括1）之间的所有数字，将该数字的子字符串的所有分区向前流，然后在每个项的开头插入该数字的子字符串