论坛徽章:: 12

1楼 [报告]

发表于 2017-06-25 23:19 |显示全部楼层

本帖最后由 523066680 于 2017-06-25 23:20 编辑

=info
Code by 523066680
2017-06
排列元素的方案参考自 http://stackoverflow.com/questions/9122315/permutations-using-perl
=cut
use List::Util qw/sum/;
our @a = (1..9);
#分组，校验的下标顺序
our @chk =
(
[1,2,3], [4,5,6], [7,8,9],
[1,4,7], [2,5,8], [3,6,9],
[1,5,9], [3,5,7],
);
#纯属冗余操作（为了前面直观）。统一 -1
grep { $_ = [map { $_-1 } @$_] } @chk; #全体 -1
#开始迭代
for ( &permute( @a ) )
{
if (check($_) == 1)
{
print join(",", @{$_}[0,1,2]),"\n";
print join(",", @{$_}[3,4,5]),"\n";
print join(",", @{$_}[6,7,8]),"\n\n";
}
}
sub permute
{
return ([]) unless (@_);
return map
{
my @cdr = @_;
my $car = splice @cdr, $_, 1;
map { [$car, @$_] } &permute(@cdr);
} 0 .. $#_;
}
sub check
{
my $a_ref = shift;
my $result = 1;
for my $ref (@chk)
{
if ( sum( map { $a_ref->[$_] } @$ref ) != 15 )
{
$result = 0;
last;
}
}
return $result;
}

复制代码

2,7,6
9,5,1
4,3,8

2,9,4
7,5,3
6,1,8

4,3,8
9,5,1
2,7,6

4,9,2
3,5,7
8,1,6

6,1,8
7,5,3
2,9,4

6,7,2
1,5,9
8,3,4

8,1,6
3,5,7
4,9,2

8,3,4
1,5,9
6,7,2

[Finished in 7.2s]

优化肯定是有的优化的，只是想看看暴力跑法。（我的strawberry perl 安装 Algorithm:

ermute 失败了，所以先借用一下别人写好的排列方案）

523066680

富足长乐

论坛徽章:: 12

2楼 [报告]

发表于 2017-06-28 20:32 |显示全部楼层

本帖最后由 523066680 于 2017-06-28 22:10 编辑

回复 19# sunzhiguolu

这个递归写的非常精简，我以前也用类似的方案写排列，不过代码比较长。
将 E_ 函数单独提取出来，把 “语法糖” 之类的东西采用更明确的方式去书写，思路就看得清楚了。
为了方便把元素 1到9 改成了a,b,c。

my @elements = qw/a b c/;
my @container = ();

#传入数组引用，左边是可选元素，右边是容器
func( \@elements, \@container );

sub func
{
#引用分别传递到 $a，$b
my ( $a, $b ) = (shift, shift);
my $last = $#$a;

#如果 @$a 的元素已经清空，打印 @$b 的内容
print join(",", @{$b}), "\n" if ( $last < 0 );

#遍历选取 @$a 的元素
for my $idx ( 0 .. $last )
{
#从 @$a 副本取出元素，添加到 @$b，进入下一层选取
func( [ @$a[0 .. $idx-1, $idx+1 .. $last] ], [ @$b, $a->[$idx] ] );
}
}

输出：

a,b,c
a,c,b
b,a,c
b,c,a
c,a,b
c,b,a

这个过程可以参考高中的排列组合/概率知识，
第一层，先从 [a,b,c] 中选1个，假设是选 b
第二层，从剩下的 [a,c] 中选取1个，假设是 a
第三层，从剩下的 [c] 中选取1个，即 c
最后得到 b,a,c

第一层有3个选项，第二层有2个选项，最后一层1个，共有 3x2x1 种排列顺序。

然后是校验的部分，

if ( @$b == 3 ) { sum( @$b[ 0, 1, 2 ] ) != 15 and return }
elsif ( @$b == 6 ) { sum( @$b[ 3, 4, 5 ] ) != 15 and return }
elsif ( @$b == 7 ) { sum( @$b[ 0, 3, 6 ] ) != 15
                     || sum( @$b[ 2, 4, 6 ] ) != 15 and return }
elsif ( @$b == 8 ) { sum( @$b[ 1, 4, 7 ] ) != 15 and return }
elsif ( @$b == 9 ) { sum( @$b[ 0, 4, 8 ] ) != 15 and return;
      print "@$b[0,1,2]\n@$b[3,4,5]\n@$b[6,7,8]\n";
      print "-----\n";
}

多个层次的判断可以减少大量冗余的排列过程，例如第一个判断：
当容器数组达到3个元素，可以计算第一行是否和为15，不是的话可以提前退回，节省后面6个元素的排列过程。
后面的判断与此类似。
最后当容器数组的元素达到9个，且最后斜线合计也为15，对符合要求的排列顺序进行输出。

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

523066680

富足长乐

论坛徽章:: 12

3楼 [报告]

发表于 2017-06-28 22:12 |显示全部楼层

回复 21# sunzhiguolu

我就是用他的代码改了函数名、拆了两部分出来而已啊
少年，你的基础 ……

我也不求积分，觉得你需要好好看书。

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

523066680

富足长乐

论坛徽章:: 12

4楼 [报告]

发表于 2017-06-28 22:40 |显示全部楼层

本帖最后由 523066680 于 2017-06-28 23:20 编辑

回复 23# sunzhiguolu

你是在递归的部分不熟悉还是都不熟悉？我一直都是自学的，觉得可以自己消化的尽量自己消化。
只有这样才能提高解决问题的能力，不然会对求助解答产生依赖。
讲真如果你基础太少，别人实在没必要从非常基础的东西跟你说起，因为那会涉及一本书的很多内容，总结是可以总结的，但别人总归有工作要做。

元素排列的部分单独提取就是这些行，可以单独执行，加个print 可以观察数组的变化过程

E_( [ 1 .. 9 ], [] );
sub E_
{
my ( $a, $b ) = @_;
#此处省略若干代码
E_( [ @$a[ 0 .. $_ - 1, $_ + 1 .. $#$a ] ], [ @$b, $a->[$_] ] )
for 0 .. $#$a;
}

复制代码

转成直白点的代码就是

func( [1..5], [] );
sub func
{
my ( $a, $b ) = (shift, shift);
print join(",", @{$b}), "\n" if ( $#$a < 0 );
for my $idx ( 0 .. $#$a )
{
my @arr = @$a;
my @brr = @$b;
push @brr, $arr[$idx]; #get element, from @arr to @brr
splice( @arr, $idx, 1 ); #delete element from @arr
func( \@arr, \@brr ); #next level
}
}

复制代码

分析代码的时候，可以自己对代码进行拆解，对中间插入 printf 来查看输出内容或者尝试 perl -d xxx.pl 进入调试模式
也可以在草稿上画出代码演算的过程，相信很多人都经历过。

而你可能并没有这么做，也许是因为懒惰，不愿意有“多余”的付出。

最后，解释权应该交给 rubyish，谁让你写的那么短