如何用perl实现求数组子集的问题呢

pp1984829

例如有一个含有n个元素的数组，列举出其所有的子集，如果用perl快速实现呢？ 高手们请出手

grshrd49

子集是什么意思？
排列 还是组合？

pp1984829

回复 2# grshrd49
例如数组 1,2,3 求出其真子集{1}{2}{3}{1,2}{1,3}{2,3}{1,2,3}


   

yinyuemi

1. perl -le '@a=(1,2,3,4,5);
   
2. my %h;
   
3. sub f{
   
4.   my $r = shift;
   
5.   $h{join " ",@$r}=1;
   
6.   if($#$r > 0){
   
7.     foreach my $index (0..$#$r){
   
8.     my @subarr = @$r;
   
9.     splice(@subarr,$index,1);
   
10.     $h{join " ",@subarr}=1;f(\@subarr)
    
11.     }
    
12.   }
    
13. };
    
14. f(\@a);
    
15. $,="\n";
    
16. print (keys %h)

复制代码

rubyish

1. #!/usr/bin/perl
   
2. use 5.018;
   
3. sub SS {
   
4.     my @R = sub {
   
5.         my ( $h, @t ) = @{ +shift };
   
6.         $h ? map { $_, [ $h, @$_ ] } __SUB__->( \@t ) : [] }->(@_);
   
7.     sort { @$a <=> @$b } @R[ 1 .. $#R ];
   
8. }
   
9. 
   
10. say "@$_" for SS [ 1 .. 5 ];

复制代码

rubyish

假设传入的数组为 :  1 .. 5

1. 1
   
2. 2
   
3. 3
   
4. 4
   
5. 5
   
6. 1 2
   
7. 1 3
   
8. 2 3
   
9. 1 4
   
10. 2 4
    
11. 3 4
    
12. 1 5
    
13. 2 5
    
14. 3 5
    
15. 4 5
    
16. 1 2 3
    
17. 1 2 4
    
18. 1 3 4
    
19. 2 3 4
    
20. 1 2 5
    
21. 1 3 5
    
22. 2 3 5
    
23. 1 4 5
    
24. 2 4 5
    
25. 3 4 5
    
26. 1 2 3 4
    
27. 1 2 3 5
    
28. 1 2 4 5
    
29. 1 3 4 5
    
30. 2 3 4 5
    
31. 1 2 3 4 5
    

复制代码

grshrd49

回复 5# rubyish

perl果然是奇葩
map { $_, [ $h, @$_ ] } __SUB__->( $n - 1, \@t ) }->(@_); 中 __SUB__ 这个是啥意思呢?

rubyish

回复 7# grshrd49


    itself, the sub

rubyish

or~

1. #!/usr/bin/perl
   
2. use 5.018;
   
3. sub SS {
   
4.     my $h = shift;
   
5.     $h ? map { $_, [ $h, @$_ ] } SS(@_) : [];
   
6. }
   
7. 
   
8. my @R = SS 1 .. 5;
   
9. say "@$_" for sort { @$a <=> @$b } @R[ 1 .. $#R ];

复制代码

line9: or

1. say "@$_" for  map $_->[1], sort { $a->[0] <=> $b->[0] }  map [ scalar @$_, $_ ], @R[ 1 .. $#R ];

复制代码

rubyish

这也许是有更容易:

1. #!/usr/bin/perl
   
2. use 5.018;
   
3. 
   
4. my @a = 'a' .. 'd';
   
5. my $t = '%0' . @a . 'b';
   
6. for ( 1 .. 2**@a - 1 ) {
   
7.     my @b = split '', sprintf $t, $_;
   
8.     say "@a[ grep $b[$_], 0 .. $#b ]";
   
9. }

复制代码