【算法】求{1，2，3}序列的全排列，邻里交换法（Java）

【算法】求{1，2，3}序列的全排列，邻里交换法（Java）

代码如下：

public class Main{
    static int count;
    static int a[]= {1,2,3};
	public static void main(String[] args) {
        f(a,0);
        System.out.println(count);
	}
    public static void f(int a[],int step) {
    	if(step==a.length-1) {
    		count++;
    		return;
    	}
    	for(int i=step;i<a.length;i++) {
    		{
    			int x=a[i];//交换
    			a[i]=a[step];
    			a[step]=x;
    		}
    		f(a,step+1);
    		{
    			int x=a[i];//还原数据
    			a[i]=a[step];
    			a[step]=x;
    		}
    	}
    }
}

图解如下：

执行过程如下：这段代码实现了对数组 a 中元素的全排列，并在 count 中记录排列的数量。下面是每一步的具体细节：

1. 初始状态：

   • a[] = {1, 2, 3}
   • count = 0

2. 调用 f(a, 0)，进入函数 f：

   • a[] = {1, 2, 3}
   • step = 0

3. 进入 for 循环，i = 0：

   • 交换 a[0] 和 a[0]（实际上没有变化）
   • 进入递归，调用 f(a, 1)：
     • a[] = {1, 2, 3}
     • step = 1

4. 进入 for 循环，i = 1：

   • 交换 a[1] 和 a[1]（实际上没有变化）
   • 进入递归，调用 f(a, 2)：
     • a[] = {1, 2, 3}
     • step = 2

5. step == a.length - 1 成立，执行 count++：

   • count = 1

6. 返回上一层递归，恢复数组 a 到初始状态：

   • a[] = {1, 2, 3}

7. 继续 for 循环，i = 2：

   • 交换 a[2] 和 a[1]，得到 a[] = {1, 3, 2}
   • 进入递归，调用 f(a, 2)：
     • a[] = {1, 3, 2}
     • step = 2

8. step == a.length - 1 成立，执行 count++：

   • count = 2

9. 返回上一层递归，恢复数组 a 到初始状态：

   • a[] = {1, 2, 3}

10. 返回上一层递归，恢复数组 a 到初始状态：

    • a[] = {1, 2, 3}

11. 继续 for 循环，i = 1：

    • 交换 a[1] 和 a[0]，得到 a[] = {2, 1, 3}
    • 进入递归，调用 f(a, 1)：
      • a[] = {2, 1, 3}
      • step = 1

12. 进入 for 循环，i = 1：

    • 交换 a[1] 和 a[1]（实际上没有变化）
    • 进入递归，调用 f(a, 2)：
      • a[] = {2, 1, 3}
      • step = 2

13. step == a.length - 1 成立，执行 count++：

    • count = 3

14. 返回上一层递归，恢复数组 a 到初始状态：

    • a[] = {2, 1, 3}

15. 继续 for 循环，i = 2：

    • 交换 a[2] 和 a[1]，得到 a[] = {2, 3, 1}
    • 进入递归，调用 f(a, 2)：
      • a[] = {2, 3, 1}
      • step = 2

16. step == a.length - 1 成立，执行 count++：

    • count = 4

17. 返回上一层递归，恢复数组 a 到初始状态：

    • a[] = {2, 1, 3}

18. 返回上一层递归，恢复数组 a 到初始状态：

    • a[] = {1, 2, 3}

19. 继续 for 循环，i = 2：

    • 交换 a[2] 和 a[0]，得到 a[] = {3, 2, 1}
    • 进入递归，调用 f(a, 1)：
      • a[] = {3, 2, 1}
      • step = 1

20. 进入 for 循环，i = 1：

    • 交换 a[1] 和 a[1]（实际上没有变化）
    • 进入递归，调用 f(a, 2)：
      • a[] = {3, 2, 1}
      • step = 2

21. step == a.length - 1 成立，执行 count++：

    • count = 5

22. 返回上一层递归，恢复数组 a 到初始状态：

    • a[] = {3, 2, 1}

23. 继续 for 循环，i = 2：

    • 交换 a[2] 和 a[1]（实际上没有变化）
    • 进入递归，调用 f(a, 2)：
      • a[] = {3, 2, 1}
      • step = 2

24. step == a.length - 1 成立，执行 count++：

    • count = 6

25. 返回上一层递归，恢复数组 a 到初始状态：

    • a[] = {3, 2, 1}

26. 返回上一层递归，恢复数组 a 到初始状态：

    • a[] = {1, 2, 3}

27. 返回上一层递归，主函数结束。

最终输出 count 的值为 6，表示数组 [1, 2, 3]