使用回溯算法排列字符串

Question

我在 Geeksforgeeks 上阅读了下面的代码，但我无法理解它是如何工作的！如果有人能形象地解释一下。那太好了！

这是代码：

static void swap(char a[], int l, int r) {
    char temp = a[l];
    a[l] = a[r];
    a[r] = temp;
}

static void permute(char a[], int l, int r) {
    if (l == r)
        System.out.println(getString(a));
    else {
        for (int i = l; i <= r; i++) {
            swap(a, l, i);
            permute(a, l + 1, r);
            swap(a, l, i); // backtrack
        }
    }
}

Answer 1

我看不出您有什么疑惑：您提供的图片向我解释得很清楚……。 :-)

终止条件（图表的底行，2 个红色和 1 个绿色项目）：如果列表只剩下一个元素需要考虑，就没有地方可以交换它。排列完成。 return

否则... 对于数组中剩余的每个项目，将该位置交换到最左边的可用位置。将 "fixed" 指针向右移动一位，并在数组的其余部分调用例程。

Overall，这只是简单地沿着数组走下去：（依次）挑选每个项目作为第一个位置；第二个（依次）挑选每个剩余的项目； ...继续到列表末尾。

这对你有什么帮助吗？

使用回溯算法排列字符串

Permutation of string using backtracking algorithm

java

algorithm

recursion

permutation

backtracking