通过一个小算法，谈谈学习如何编写程序

给定一个数字列表，返回其所有可能的排列

输入：[1,2,3]
输出：
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

假定各个数字不相同

给出核心代码

　　 private void dfs(int[] nums,

                     boolean[] visited,
                     list<integer> permutation,
                     list<list<integer>> results) {
        if (nums.length == permutation.size()) {
            results.add(new arraylist<integer>(permutation));
            return;
        }
       
        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
           
            permutation.add(nums[i]);
            visited[i] = true;
            dfs(nums, visited, permutation, results);
            visited[i] = false;
            permutation.remove(permutation.size() - 1);
        }
    }

考虑int[] nums={1,2,3,4}情况

——————————————————————————————————————————————

可以看下面各个量的变化情况，当看不懂算法的时候，可以用这种方法，自己一步一步模拟程序做了什么，就能明白代码的含义了

在这个小例子中，visted【】数组存放的是，1234是否在permutation中的状态，

对于1234这四个数，visited【0】=false，就代表1没在permutation中

1234会不断添加到permutation中，并且当4个数字都进入p中时，会得到一个结果；

——————————————————————————————————————————————

在模拟的过程中，我们明白各个变量发生了什么，所代表的意义

然后对于比较有代表性的几个位置，看看程序发生了什么

——————————————————————————————————————————————

1     观察程序回到dfs（tttf，1230）时

v2 变成f

p   变成1200

循环进入f3

而此时4不在p中

4进入p中

然后重新调用

dfs（ttft，1240）

可以预见，下一个进入result的就是1243

————————————————————————————————

2    继续观察程序运行到dfs（tttt，1432）

首先会将1432add进入result

然后回到dfs的位置

dfs（tttf，1430）的f1循环中，

继续运行

v1变成f  p变成143 此时v是 tftt然后

f2 t

f3 t

此时 dfs（tttf，1430）运行结束 a8位置

给出a8之前的三行

f2 f

p143

v2 t tftt

然后我们继续模拟程序

v2 f tfft

p14

f3 t

说明某个dfs已经完成了全部循环，这个dfs的位置应该是最近的一个没有被标号的dfs

因为有标号的，说明都被执行完了

goto a9

我们回到了 dfs(tfft,1400)a9

f3 f

p14

v3 t tfft

继续模拟程序

v3 f

p1

此时 dfs(tfft,1400)所在的循环也结束了

goto a10

说明dfs(tfff,1000) a10也执行结束了

观察dfs(tfff,1000) a10上面的三行代码

f0 f

p1

v0 f

继续进行

v0 f ffff

p0000

f1 f

p2

v1 t

dfs（ftff，2000）

——————————————————————————————————————————————————————————————

通过这两处 我们完全可以明白这些代码的意义了

对于任何一位上的某个数字a，在它进入p之后，对于这一位来讲，没进入p而比a更靠后的数字，会添加进p

而对于当添加一个元素进入后，它的下一位会从重新又从头去寻找v[i] t，也就是没有进入p的数字

而对于填入某个位置数字后的dfs执行完成了，如果后一位的数字都比前一位的数字在原数组更靠前，那么就会出现

每退掉一位，回到前一个dfs，而将要退掉这个位置的数字，而之前的数字，在原数组的位置都比这个数字靠前，所以之后的循环不会再有数字进入

如果是1432，那么会变成2000

如果是4321，那么会变成dfs（fttt，4000）结束，整个程序结束

——————————————————————————————————————————————————————————————

 

而学习其他代码的过程也类似

看懂了代码以后，尝试用自然程序做了什么说出来，如果能说明白发生了什么事，也就说明看懂了

然后再把自己想要完成的事梳理一下，拆解成一步一步要做的事，再用代码使其重新实现

学习代码的过程：

　　模拟程序代码逐条运行 ——》尽量提炼出代码块的作用 ——》用自然语言 说明算法做了什么

而编写代码的过程：

　　分析问题——》提出完成算法的各个步骤 ——》逐条编写代码完成各个步骤 ——》调试，带入测试数据

 

下面给出模拟程序运行时，各个变量的变化情况

dfs(ffff,0000)  //dfs(nums,ffff,,)为了方便 只写最频繁变化的两个参数

f0 f       //f(0) 为了方便写成 f0 v[0]是f

p1        //permutation={1} 为了方便写成 p1

v0 t     tfff      //v[0]改成0 visited变成 tfff

dfs(tfff,1000) a10

f0 t 　　

f1 f

p12

v1 t 

dfs(ttff,1200) a3

f0 t

f1 t

f2 f

p123

v2 t

dfs(tttf,1230) a1

f0 t

f1 t

f2 t

f3 f

p1234

v3 t

dfs(tttt,1234)

result 1234 //这里的dfs直接结束了 能找到

v3 f tttf

p123

goto a1 这里其实是方法a的 for循环结束了 返回a所在位置，继续下一行

v2 f ttff

p12

f3 f

p124

v3 t

dfs(ttft,1240) a2

f0 t

f1 t

f2 f

p1243

v2 t

dfs(tttt,1243)

result  1243

v2 f ttft

p124

f3 t

goto a2

v3 f ttff

p12

goto a3

v1 f tfff

p1 

f2 f

p13

v2 t tftf

dfs(tftf,1300) a6

f0 t

f1 f

p132

v1 t

dfs(tttf,1320) a4

f0 t

f1 t

f2 t

f3 f

p1324

v3 t tttt

dfs(tttt,1324)

result 1324

v3 f tttf

p132 

goto a4

v1 f tftf

p13

f2 t

f3 f

p134

v3 t tftt

dfs(tftt,1340) a5

f0 t

f1 f

p1342

v1 t tttt

dfs(tttt,1342)

result 1342

v1 f tftt

p134

f2 t

f3 t

goto a5

v3 f tftf

p13

goto a6

v2 f tfff

p1

f3 f

p14

v3 t tfft

dfs(tfft,1400)a9

f0 t

f1 f

p142

v1 t ttft

dfs(ttft,1420) a7

f0 t

f1 t

f2 f

p1423

v2 t tttt

dfs(tttt,1423)

result 1423

v2 f ttft

p142 

f3 t

goto a7

v1 f tfft

p14

f2 f

p143

v2 t tftt

dfs(tftt,1430) a8

f0 t

f1 f

p1432

v1 t

dfs(tttt,1432)

return 1432

v1 f tftt

p143

f2 t

f3 t

goto a8

v2 f tfft

p14

f3 t

goto a9

v3 f tfff

p1

goto a10

v0 f ffff

p000

f1 f

p2

v1 ftff

dfs(ftff,2000)

我们可以预见 下一个就是2134

我们已经完全可以预见程序将要完成什么了

也就是此时此刻，我们看懂了这段代码的含义