|
|
发表于 2017-4-26 14:13:01
|
显示全部楼层
模式计算-迭代法
本帖最后由 523066680 于 2017-5-15 12:35 编辑
编辑/整理：523066680@163.com
日期：2017-05
序
通过迭代方式获得排列的方案，参考自《Higher-Order Perl》
概念
假设有4个元素: @arr = (a, b, c, d)，下标为 0 1 2 3，每提取一个元素，
数组重新定义，下标从0开始。排列和下标的提取关系：
a b c d -> 0 0 0 0
a b d b -> 0 0 1 0
a c b d -> 0 1 0 0
a c d b -> 0 1 1 0
a d b c -> 0 2 0 0
...
注意这里数字的变化和进制换算、递增非常相似，区别在于，每一位的进制是不同的：
末位始终为0，
倒数第二位最大为1(0,1)，
倒数第三位最大为2(0,1,2)，
倒数第四位最大为3(0,1,2,3)
一共能产生 432*1 种模式(pattern) （刚好对应24种排列情况）
不同模式的生成和换算
先设计一种换算函数，对于传入的任意数字，计算出对应的模式：
my @elements = qw/a b c d/; #元素
my $seats = $#elements + 1; #数量
my @order = (0) x $seats; #初始模板
to_pattern(5, $seats, \@order);
print join(",", @order);
sub to_pattern #转换器
{
my ($num, $seats, $o_ref) = @_;
my $mod;
for my $div ( 1 .. $seats )
{
$mod = $num % $div;
$num = int($num / $div);
$o_ref->[-$div] = $mod; #倒序填入
}
} |
输出: 0,2,1,0
将模式应用到排列顺序
再写一个函数将 模式应用于顺序地提取数组元素
my @elements = qw/a b c d/;
my $seats = $#elements + 1;
my @order = (0, 2, 1, 0);
apply(\@elements, \@order);
sub apply
{
my ($e_ref, $o_ref) = @_;
my @temp = @$e_ref;
my @final;
for my $idx ( @$o_ref )
{
push @final, splice( @temp, $idx, 1 );
}
print join(",", @final),"\n";
} |
输出：a,d,c,b
这样，不管想要哪一个序列，只要通过类似进制换算的方法算出模式，按模式提取即可
枚举所有情况的代码：
use strict;
my @elements = qw/a b c d e/;
my $seats = $#elements + 1;
my @order = (0) x $seats;
for my $n ( 0 .. factorial($seats)-1 )
{
my @result;
to_pattern($n, $seats, \@order);
apply( \@elements, \@order, \@result );
print join(",", @result), "\n";
}
sub to_pattern
{
my ($n, $seats, $o_ref ) = @_;
my $mod;
for my $div ( 1 .. $seats )
{
$mod = $n % $div;
$n = int($n / $div);
$o_ref->[-$div] = $mod; #从右边向左填入
}
}
sub apply
{
my ($e_ref, $o_ref, $result) = @_;
my @temp = @$e_ref;
for my $idx ( @$o_ref )
{
push @$result, splice( @temp, $idx, 1 );
}
}
sub factorial
{
my $v = shift;
return ($v > 1) ? $v*factorial($v-1) : 1;
} |
[Finished in 0.9s] |
评分
-
查看全部评分
|
发表于 2017-4-8 11:24:59
发表于 2017-4-26 20:43:09
发表于 2019-3-29 23:33:29