在 Java 中使用递归的字符串排列 [英] String permutations using recursion in Java

问题描述

我遇到了 THIS 帖子，该帖子非常努力地解释了打印所有字符串的递归解决方案.

I came across THIS post which tried very hard to explain the recursive solution to print all string.

public class Main {
    private static void permutation(String prefix, String str) {
        int n = str.length();
        if (n == 0)
            System.out.println(prefix);
        else {
            for (int i = 0; i < n; i++)
                permutation(prefix + str.charAt(i),
                        str.substring(0, i) + str.substring(i + 1));
        }
    }

    public static void main(String[] args) {
        permutation("", "ABCD");
    }
}

但是当我们开始从堆栈中弹出时，我仍然无法获得零件.例如，递归一直进行到 permutation("ABCD","")，在那里遇到基本情况并打印 ABCD.但是现在会发生什么?我们从函数调用堆栈中弹出 permutation(ABC",D").我们如何处理这个等等?

But still I am not able to get the part when we start popping off the stack. For example, recursion goes all the way till permutation("ABCD",""), where base case meets and it prints ABCD. But what happens now? We pop off permutation("ABC","D") from function call stack. What we do with this and so on?

有人可以帮忙解释一下吗?

Can someone please help explain a bit?

此外，我需要一些有关此时间复杂度的提示.不像完整的计算，而是一些提示.

Also, I need some pointers on the time complexity of this. Not like complete calculation but some hints.

推荐答案

更简单的例子:permutation("", "ABC")，将空字符串表示为 *:

Easier example: permutation("", "ABC"), representing empty string as *:

* ABC + A BC + AB C - ABC *
      |      |
      |      ` AC B - ACB *
      |
      + B AC + BA C - BAC *
      |      |
      |      ` BC A - BCA *
      |
      ` C AB + CA B - CAB *
             |
             ` CB A - CBA *

请注意，这看起来像一棵横着放的树.的确，它叫做一棵树.当我们开始时，我们会进入("A", "BC")状态；我们继续调用("AB", "C")，最后调用("ABC", "").在这里我们打印我们的输出.然后我们记得我们还有未完成的事情，我们回到一个循环，但是上一层的循环只有一个循环.所以我们也完成了，回到("A", "BC")层；"BC" 中有两个元素，我们只完成了 "B"，所以现在轮到 "C":我们调用 ("AC", "B")，然后调用 ("ACB", "").现在 ("A", "BC") 下的所有循环都完成了......但是等等，还有工作要做！因为 ("", "ABC") 还有两个字母要处理.就这样，一个分支一个分支，我们通常所说的深度优先搜索".

Note that this looks like a tree laid on its side. Indeed, it called a tree. When we start, we will enter ("A", "BC") state; we proceed to call ("AB", "C"), and finally ("ABC", ""). Here we print our output. Then we remember we have unfinished business, we return to a loop, but the loop in the previous level only had one cycle. So we're done there as well, and return back to ("A", "BC") level; there are two elements in "BC" and we've only done the "B", so it's now "C"'s turn: we call ("AC", "B"), which then calls ("ACB", ""). Now all the loops under ("A", "BC") are done... But wait, still work to do! Because ("", "ABC") still has two more letters to process. And so it goes, branch by branch, in what we usually call "depth-first search".

在每个级别中都有一个循环.循环缩小了(我们在左边的粗分支中迭代了 3 次，然后在下一层迭代了 2 次，然后只有一次)但仍然存在一个循环.所以总的来说，我们做了 n * (n - 1) * (n - 2) * ... * 2 * 1 次迭代.O(N!)?

In each level is a loop. The loop shrinks (we iterate 3 times in the thick branch at the left, then 2 in the next level, then only one) but still there is a loop. So in total, we do n * (n - 1) * (n - 2) * ... * 2 * 1 iterations. O(N!)?

这篇关于在 Java 中使用递归的字符串排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！