使用回溯算法对字符串进行排列

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 个绿色项目）： 如果列表只剩下一个元素需要考虑，则没有地方可以交换它。排列完成。 返回

否则... 对于数组中剩余的每个项目，将该位置交换到最左侧的可用位置。将“固定”指针向右移动一位，然后对数组的其余部分调用例程。

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

这对你来说有什么好处吗？

Answer 2

您尚未包含执行该函数的驱动程序代码，即

permute(a[],0,len)，其中 len 是字符串的长度。从 l=0 和 r=len 开始，并借助图表跟踪代码。沿着图中的每个箭头阅读交换语句。使用的技术称为回溯，一个重要的数据结构概念称为深度优先搜索。 （这 2 个交换语句用于在探索到底部的每个分支后返回到您开始的位置）。你从顶部开始，一直向左走，直到到达左下角。然后向上一步，执行下一个左叶（在本例中，每个源节点有 3 个叶），直到每一层到达最右边的叶。 （这里有 3 个级别）这有点有趣，但该图是最简单的。 希望这会有所帮助，但需要大量的自助。