算法设计与分析5.6生成排列两种过程的讨论

第一种算法

算法 5.7   PERMUTATIONS1
输入: 正整数 n
输出: 数1,2,...,n的所有可能排列
    1. for j <- 1 to n
    2.      p[j] <- j
    3. end for
    4.      perm1(1)
过程  perm1(m)
    1. if m = n then output P[1...n]
    2. else
    3.      for j <- m to n
    4.           互换P[j] 和 P[m]
    5.           perm1(m + 1)
    6.           互换p[j] 和 p[m]
    7.          comment: 这是 P[m...n] = m,m+1,...,n
    8.      end for
    9. end if   

这里第7句的comment是说明第6句执行后数组的状态。其实第6部操作就是想恢复第4步操作，防止重复.

讨论： 令n=3,讨论其输出顺序

j = 1 to 3  comment:m = 1
    j = 1   comment:m = 1
    (1, 2, 3)
    P(2)
        j = 2 to 3  comment: m = 2
            j = 2   comment: m = 2
            (1, 2, 3)
            P(3)
                Print("1, 2, 3")
            {1, 2, 3}

            j = 3   comment: m = 2
             (1, 3, 2)
             P(3)
                 Print("1, 3, 2")
             {1, 2, 3}
    j = 2    comment:m = 1
    (2, 1, 3)
    P(2)
        j = 2 to 3  comment: m = 2
            j = 2    comment: m = 2
            (2, 1, 3)
            P(3)
                Print("2, 1, 3")
            {2, 1, 3}
            
           j = 3   comment: m = 2
            (2, 3, 1)
            P(3)
               Print("2, 3, 1")
           {2, 1, 3}
    j = 3  comment:m = 1
    (3, 1, 2)
    P(2)
        j = 2 to 3  comment: m = 2
            j = 2    comment: m = 2
            (3, 1, 2)
            P(3)
                Print("3, 1, 2")
            {3, 1, 2}
            
           j = 3   comment: m = 2
            (3, 2, 1)
            P(3)
               Print("3, 2, 1")
     算法结束

上面如（1，2，3）代表第4句执行的结果，{1,2,3}代表第5句执行的结果。Print()代表打印输出排列。comment： m = i (1,2)指的是注释，目的是想要读者注意m的取值，应为是P[ j ] 和P[ m ] 交换。

第二种算法

算法5.8 PERMUTATIONS2
输入: 正整数 n
输出: 数1,2,...,n 的所有可能排列
    1. for j <- 1 to n
    2.     P[j] <- 0
    3. end fo
    4. perm2(n)
过程  perm2(m)
    1.  if m = 0 then output P[1...n]
    2.  else
    3.      for j <- 1 to n
    4.          if P[j] = 0 then
    5.              P[j] <- m
    6.              perm2(m - 1)
    7.              P[j] <- 0
    8.          end if
    9.      end for
    10.  end if

这里一开始置零，表示是自由的位置.

讨论： 令n=3,讨论其输出顺序

j = 1 to 3
    j = 1   comment: m = 3
        (3, _, _)
        P(2)
            j = 1 to 3   comment: m = 2
                j = 1  comment: P[1]位置已经被占领
                j = 2  comment: m = 2
                    (3, 2, _)
                    P(1)   comment: m = 1
                        (3, 2, 1)
                        Print("3, 2, 1")
                    {3, _, _}
                j = 3  comment: m = 2
                    (3, _, 2)
                    P(3)   comment: m = 1
                        (3, 1, 2)
                        Print("3, 1, 2")
                    {3, _, _}
        {_, _, _}
   j = 2   comment: m = 3
       (_, 3, _)
       P(2)
            j = 1 to 3  comment: m = 2
                j = 1
                    (2, 3, _)
                    P(1)  comment: m = 1
                        (2, 3, 1)
                        Print("2, 3, 1")
                    {_, 3, _}
                j = 2   comment: P[2]位置已经被占领
                j = 3  comment: m = 2
                    (_, 3, 2)
                    P(1) comment: m = 1
                        (1, 3, 2)
                        Print("1, 3, 2")
                    {_, 3, _}
      {_, _, _}
  j = 3  comment: m = 3
    (_, _, 3)
     P(2)
          j = 1 to 3 comment: m = 2
              j = 1
                  (2, _, 3)
                  P(1)   comment: m = 1
                      (2, 1, 3)
                      Print("2, 1, 3")
                 {_, _, 3}
              j = 2
                  (_, 2, 3)
                  P(1)   comment: m = 1
                      (1, 2, 3)
                      Print("1, 2, 3")
                  {_, _, 3}
              j = 3  comment: P[3]位置已经被占领
      {_, _, _}
 算法结束

上面的过程分析如(3, _, _)的圆括号里的数是第5句执行完之后的结果, 为了看起来更直观，“自由”的位置我写成下划线 _ ，实际上那个位置的值为0。然后comment后面是我想强调的，比如m的值，因为第5句操作会把m 放到 P[ j ]上。还有有些注释比如 comment: P[1]位置已经被占领 ，这个时候不满足第4句的判断 if P[ j ] = 0,所以不会执行递归操作。无法得到结果。P（1） 时候 “自由” 的位置只有一个我就不赘述了。{}是第七句执行“P[j] <- 0 ”后的结果，其实这里 _ 的位置是0.