使用回溯算法对字符串进行排列 [英] Permutation of string using backtracking algorithm

问题描述

我正在阅读下面有关Geeksforgeeks的代码，但是我无法完全理解它的工作原理！如果有人可以用图片说明.那就太好了！

I was reading the code below on Geeksforgeeks, but I just can't wrap my head around how it works! If anyone can explain it pictorially. That'd be great!

这是代码:

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
        }
    }
}

推荐答案

我看不到您感到困惑的地方:您提供了一张图片，非常清楚地向我解释了它. :-)

I don't see where you're confused: you provided a picture that explains it quite clearly ... to me. :-)

终止条件(图表的底行，2个红色和1个绿色项目): 如果列表中只剩下一个要考虑的元素，则无处可换.排列完成. 返回

Termination condition (bottom row of your diagram, 2 red & 1 green items): if the list has only one remaining element to consider, there's nowhere to swap it. The permutation is done. return

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

Otherwise ... For each item remaining in the array, swap that position into the left-most available spot. Move the "fixed" pointer one spot to the right, and call the routine on the rest of the array.

总体，它简单地沿着数组移动:依次选择每个项目作为第一个位置；依次挑选每个剩余的物品； ...继续到列表末尾.

Overall, this simply walks down the array: pick each item (in turn) for the first position; pick each remaining item (in turn) for the second; ... continue through the end of the list.

这能为您清除一切吗?

这篇关于使用回溯算法对字符串进行排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！