怎样生成全排列?

我前面写过一种方法生成全排列,现在看用DP的方法解决。
参考How to generate permutations  看前面的那种解法。


DP的思路就是生成N个数的全排列，先考虑生成前面N-1个数字的全排列，然后把最后一个数字插入上一步每个结果的每个缝隙中，形成最后的结果。用perl比较好操纵数组，写起来的程序比较简单。(可惜这个博客不支持perl语法高亮啊）

  use strict;
  use warnings;


  sub permutation {
      my (@array) = @_;
      my $length =  scalar @array;
      if($length == 1){
          #如果数组就一个元素，返回的结果集合里面只有一个单元素数组
          return [\@array];
      }else {
          #取出最后一个元素
          my $tail = pop(@array);
          #求解N-1个数字的全排列
          my $sub_results = permutation(@array);
          my $new_results = [];
          foreach my $sub_result (@$sub_results){
             my $pos = 0;
             #取出的最后的那个元素可以插在0,1..$length-1等处
             while($pos < $length){
              my @new_result = @$sub_result;
              #插入尾元素，形成新的数组
              splice(@new_result, $pos, 0, $tail);
              $pos++;
              #收集结果
              push @$new_results, \@new_result;
             }
          }
          return $new_results;
      }
  }

  sub main {
      my @a = (6,7,8,9);
      my $results = permutation(@a);
      foreach my $result (@$results){
          print join(',', @$result) . "\n";
      }
  }

  main;

输出如下:
9,8,7,6
8,9,7,6
8,7,9,6
8,7,6,9
9,7,8,6
7,9,8,6
7,8,9,6
7,8,6,9
9,7,6,8
7,9,6,8
7,6,9,8
7,6,8,9
9,8,6,7
8,9,6,7
8,6,9,7
8,6,7,9
9,6,8,7
6,9,8,7
6,8,9,7
6,8,7,9
9,6,7,8
6,9,7,8
6,7,9,8
6,7,8,9


相比之下,这种思路要简单多了. 性能就要在考虑了.