关于perl的排列组合问题

venturexu

今天碰到一个问题,特来请教
有8个数,(01,13,15,18,33,55,99,109),从中取出4个,列出所有的组合,组合中不能有重复的,就是说01,13,15,18和18,13,15,01算一种,大家看看这个怎么弄,我查了很多算法,没有想到好的办法.

flw

刚写了一个，不太好。估计用 map 可以在 3 行之内搞定。

1. use strict;
   
2. use warnings;
   
3. 
   
4. sub foo($$$);
   
5. 
   
6. my @array = (01,13,15,18,33,55,99,109);
   
7. 
   
8. foo(\@array, 4, []);
   
9. 
   
10. sub foo($$$){
    
11.     my ($rarry, $level, $result) = @_;
    
12. 
    
13.     unless($level){
    
14.         print join ',', @$result, "\n";
    
15.         return;
    
16.     }
    
17. 
    
18.     foreach my $i (0..@$rarry-1){
    
19.         push @$result, $rarry->[$i];
    
20.         foo( [@$rarry[0..$i-1], @$rarry[$i+1..$#$rarry]], $level-1, $result );
    
21.         pop @$result;
    
22.     }
    
23. }

复制代码

shucho

我运行了一下，发现有重复的

shihyu

这是使用 Recursive call 去写吗??
sub foo($$$){

}

可以写成下面那样吗??
sub foo{
}

($$$) 加上这用意为什么??? 是因为前面有sub foo($$$); 宣告吗??

foo(\@array, 4, []); #  参数 [] 是什么意思???

谢谢

flw

原帖由 shucho 于 2006-10-10 19:39 发表
我运行了一下，发现有重复的

没有的。

flw

原帖由 shihyu 于 2006-10-10 20:01 发表
这是使用 Recursive call 去写吗??
sub foo($$$){

}

可以写成下面那样吗??
sub foo{
}

($$$) 加上这用意为什么??? 是因为前面有sub foo($$$); 宣告吗??

foo(\@array, 4, []); #  参数 [] 是什么意 ...

sub foo($$$) 这个是原型，参见 perldoc perlsub
原型的作用是在调用时进行强制性的参数检查。不过调用时前面加 & 可以规避检查。
[] 是匿名数组。

shucho

原帖由 flw 于 2006-10-10 21:08 发表

没有的。

1. 
   
2. use strict;
   
3. use warnings;
   
4. 
   
5. sub foo($$$);
   
6. 
   
7. my @array = (01,13,15,18);
   
8. 
   
9. foo(\@array, 4, []);
   
10. 
    
11. sub foo($$$){
    
12.     my ($rarry, $level, $result) = @_;
    
13. 
    
14.     unless($level){
    
15.         print join ',', @$result, "\n";
    
16.         return;
    
17.     }
    
18. 
    
19.     foreach my $i (0..@$rarry-1){
    
20.         push @$result, $rarry->[$i];
    
21.         foo( [@$rarry[0..$i-1], @$rarry[$i+1..$#$rarry]], $level-1, $result );
    
22.         pop @$result;
    
23.     }
    
24. }
    

复制代码

如果是4个元素的数组，那么应该只有一种组合，但是如果运行一下，会发现
$ perl prog | wc -l
      24
这应该不对吧

flw

哦，我搞成排列了，不是组合。

shucho

我想到一个很笨的办法。

一开始还是做排列组合，定义中间结果为一个HASH, 数据结构为：
HASH =
{
[01,13,15,18] => 6, ## 6 = 0+1+2+3，为下标的和
[13,01,15,18] => 6, ## 6 = 1+0+2+3, 同上
[...] => N,
...,
...
}
然后反转一下HASH，这样就得到了最终结果(values HASH)
虽然很土，但是应该奏效。

我看了一下算法书，可能是图论(有向图)或者计算几何(多边形)的内容，不过我不是学计算机的，不是很清楚，别笑我

[ 本帖最后由 shucho 于 2006-10-10 22:20 编辑 ]

shihyu

原帖由 shucho 于 2006-10-10 22:19 发表
我想到一个很笨的办法。

一开始还是做排列组合，定义中间结果为一个HASH, 数据结构为：
HASH =
{
[01,13,15,18] => 6, ## 6 = 0+1+2+3，为下标的和
[13,01,15,18] => 6, ## 6 = 1+0+2+3, 同上
[.. ...

6 = 0+1+2+3
6 = 1+0+2+3

用组数组存放组合数总和如果又出现一样总和就不要

1. sub foo($$$){
   
2. 
   
3. 我是觉得可以在这里面直接判断 用 if + 数组判断
   
4. }

复制代码

[ 本帖最后由 shihyu 于 2006-10-10 22:58 编辑 ]