首页 手机软件 手机游戏 单机游戏 资讯文章 专题下载 游戏合集 文章合集 php下载 php教程 电脑软件
+ -
当前位置：首页 → 问答吧 → 请教一个全排列的算法

请教一个全排列的算法

时间：2010-10-27

来源：互联网

本帖最后由 yybmsrs 于 2010-10-27 18:03 编辑
  1.   #!/usr/bin/perl -w
  2.   # mjd_permute: permute each word of input
  3.   use strict;
  4.   sub factorial($);  # forward reference to declare prototype
  5.   
  6.   while (<>) {
  7.       my @data = split;
  8.       my $num_permutations = factorial(scalar @data);
  9.       for (my $i=0; $i < $num_permutations; $i++) {
  10.           my @permutation = @data[n2perm($i, $#data)];
  11.           print "@permutation\n";
  12.       }
  13.   }
  14.   
  15.   # Utility function: factorial with memoizing
  16.   BEGIN {
  17.     my @fact = (1);
  18.     sub factorial($) {
  19.         my $n = shift;
  20.         return $fact[$n] if defined $fact[$n];
  21.         $fact[$n] = $n * factorial($n - 1);
  22.     }
  23.   }
  24.   
  25.   # n2pat($N, $len) : produce the $N-th pattern of length $len
  26.   sub n2pat {
  27.       my $i   = 1;
  28.       my $N   = shift;
  29.       my $len = shift;
  30.       my @pat;
  31.       while ($i <= $len + 1) {   # Should really be just while ($N) { ...
  32.           push @pat, $N % $i;
  33.           $N = int($N/$i);
  34.           $i++;
  35.       }
  36.       print "---@pat---\n";
  37.       return @pat;
  38.   }
  39.   
  40.   # pat2perm(@pat) : turn pattern returned by n2pat( ) into
  41.   # permutation of integers.  XXX: splice is already O(N)
  42.   sub pat2perm {
  43.       my @pat    = @_;
  44.       my @source = (0 .. $#pat);
  45.       my @perm;
  46.       push @perm, splice(@source, (pop @pat), 1) while @pat;
  47.       print "+++@perm+++\n";
  48.       return @perm;
  49.   }
  50.   
  51.   # n2perm($N, $len) : generate the Nth permutation of $len objects
  52.   sub n2perm {
  53.       pat2perm(n2pat(@_));
  54.   }
复制代码
输入i love you，输出如下：
  1. ---0 0 0---
  2. +++0 1 2+++
  3. i love you
  4. ---0 1 0---
  5. +++0 2 1+++
  6. i you love
  7. ---0 0 1---
  8. +++1 0 2+++
  9. love i you
  10. ---0 1 1---
  11. +++1 2 0+++
  12. love you i
  13. ---0 0 2---
  14. +++2 0 1+++
  15. you i love
  16. ---0 1 2---
  17. +++2 1 0+++
  18. you love i
复制代码
不明白的是n2pat和pat2perm算法的原理是什么呢？

作者: yybmsrs   发布时间: 2010-10-27

cpan有类似的模块·

作者: wfnh   发布时间: 2010-10-27

相关阅读 更多

热门阅读

热门下载

更多
关于本站 免责申明 联系我们

Copyright 2006-2020 php爱好者(phpfans.net) All Rights Reserved.备案号：湘ICP备2023016114号-2

本站为非盈利性网站，不接受任何广告。本站所有资源均由网友上传，如有侵权，请发邮件至 [email protected] phpfans.net