Schrift
Wiki:Tipp zum Debugging: use Data::Dumper; local $Data::Dumper::Useqq = 1; print Dumper \@var;
[thread]12655[/thread]

Pythagorische Tripel

Leser: 5


<< |< 1 2 >| >> 19 Einträge, 2 Seiten
Ronnie
 2008-10-19 15:57
#115628 #115628
User since
2003-08-14
2022 Artikel
BenutzerIn
[default_avatar]
Ich sammle gerade Beispiele für die Leistungsfähigkeit von Skriptsprachen. Ein Beispiel ist das Erzeugen pythagorischer Tripel. Leider gefällt mir die Perl-Lösung gar nicht, weil sie der 'klassischen' Lösung entspricht:
Code (perl): (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#!/usr/bin/perl

use strict;
use warnings;

use Data::Dumper;
use Carp;

sub gen_triangles {
    my $max = shift || 10;
    my @set;
    
    for my $c (1..$max) {
        for my $b (1..$c) {
            for my $a (1..$b) {
                push @set, [$a, $b, $c] if $c**2 == $b**2 + $a**2;
            }
        }
    }    
    return \@set;
}

print Dumper gen_triangles;

Zum Vergleich mal das selbe (als ListComprehension) in Python:
Code: (dl )
print [(a,b,c) for c in range(20) for b in range(c) for a in range(b) if c**2==a**2+b**2]

oder in Haskell (ghci):
Code: (dl )
1
2
let triangles = [ (a, b ,c) | c <- [1..], b <- [1..c], a <- [1..b], a^2+b^2==c^2 ]
take 10 triangles

Die Haskell Variante nutzt lazy-evaluation, sodass die Definition tatsächlich für 1 bis unendlich möglich ist.

Eine Ruby-Variante würde der obigen Perl5 Version gleichen, aber durch das yield-Statement könnte man es wenigstens als Iterator nutzen.

Ich suche eine elegantere Version in Perl5, würde aber auch eine in Perl6 nehmen?!
moritz
 2008-10-19 22:26
#115634 #115634
User since
2007-05-11
923 Artikel
HausmeisterIn
[Homepage]
user image
Wenn du in Perl 6 eine lazy list bauen willst, kannst du dafür gather/take nehmen:

Code: (dl )
1
2
3
4
5
6
7
8
my @pyt = gather {
for 1..20 -> $c {
for 1..$c -> $b {
my $a = sqrt($c**2 - $b**2);
take [$a, $b, $c] if $a == int($a);
}
}
}
lichtkind
 2008-10-19 22:37
#115635 #115635
User since
2004-03-22
5680 Artikel
ModeratorIn + EditorIn
[Homepage]
user image
ich glaub das geht auch eleganter aber ich find grad nicht die stelle in den syn.
Wiki:Tutorien in der Wiki, mein zeug:
kephra, baumhaus, garten, gezwitscher

Es beginnt immer mit einer Entscheidung.
LanX-
 2008-10-19 23:08
#115636 #115636
User since
2008-07-15
1000 Artikel
BenutzerIn

user image
Hi Ronnie

IMHO kannste es kaum kürzer in Perl5 hinschreiben, z.B. weil man postfix-For nicht kaskadieren kann.

Mit greps und maps könnte man tricksen, dass sähe aber kaum elegant aus.

Hier zeigt sich halt das Haskell und Python aus nem wissenschaftlichen Milieu stammen.


Wenn man diese Mathematische Notation denn öfter bräuchte, könnte man sich problemlos ein entsprechendes Modul basteln auch mit lazy evaluation.

Tja ... schade nur das du dein HoP nicht mehr hast *fg*

;) Rolf


PS: zumindest könntest du schadlos die "my"s einsparen, ist AFAIK redundant.
LanX-
 2008-10-19 23:48
#115637 #115637
User since
2008-07-15
1000 Artikel
BenutzerIn

user image
einzeiler sind nicht zwingend unelegant
Code (perl): (dl )
1
2
3
for $c (1..10) { for $b (1..$c) { for $a (1..$b) {
    print $c,$b,$a  if $c**2 == $b**2 + $a**2;
} } }


BTW: pythagoreische Tripel lassen sich deutlich effizienter finden als mit diesem Brute Force Ansatz.
Ronnie
 2008-10-20 00:37
#115640 #115640
User since
2003-08-14
2022 Artikel
BenutzerIn
[default_avatar]
Danke an alle Poster!

LanX-+2008-10-19 21:48:21--
BTW: pythagoreische Tripel lassen sich deutlich effizienter finden als mit diesem Brute Force Ansatz.

ja: http://en.wikipedia.org/wiki/Pythagorean_triple#Ot...

wobei es mir ja eher um den Code als um die Tripel ging.
topeg
 2008-10-20 01:13
#115642 #115642
User since
2006-07-10
2611 Artikel
BenutzerIn

user image
Wer will es denn einfach, wenn es auch kompliziert geht ;)
Code (perl): (dl )
1
2
3
4
5
6
7
8
9
10
sub gen_triangles {
  my $max = shift || 10;
  my @set;
  my($x,$y,$z)=(1,1,1);
  while($z<=$max && $x<=$max){
    push @set, [$z, $y, $x] if $x**2 == $y**2 + $z**2;
    if($y>$z){$z++}else{if($x>$y){$y++;$z=1}else{$x++;$y=$z=1}}
  }
  return \@set;
}

Seid nicht so verschwenderisch mit Schleifen, die wachsen nicht auf Bäumen ;)
LanX-
 2008-10-29 15:48
#115819 #115819
User since
2008-07-15
1000 Artikel
BenutzerIn

user image
Hei Ronnie,

Ronnie+2008-10-19 13:57:41--
Zum Vergleich mal das selbe (als ListComprehension) in Python:
Code: (dl )
print [(a,b,c) for c in range(20) for b in range(c) for a in range(b) if c**2==a**2+b**2]

oder in Haskell (ghci):
Code: (dl )
1
2
let triangles = [ (a, b ,c) | c <- [1..], b <- [1..c], a <- [1..b], a^2+b^2==c^2 ]
take 10 triangles


Um deinen Bedürfnis nach ListComprehension nachzukommen anbei ein wenig Code wie man das nachbauen kann, letztendlich sind es nur verschachtelte Schleifen die eine Liste zurückgeben.

Was du in Python syntaktisch einsparst sind die Klammern, ob dadurch Python übersichtlicher wird als Perl is a Matter of Debate. Semantisch ist es IMHO das gleiche!


Code (perl): (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#!/usr/bin/perl

use Data::Dumper;

my $max=10;


### Straight forward


sub list (&){
    my $code_ref=shift;
    &$code_ref;
    return @_;
}


@x= list { for $c (1..10){ for $b (1..$c){ for $a (1..$b){
           push @_, [$c,$b,$a]  if $c**2 == $b**2 + $a**2;
    } } } };

print Dumper \@x;



### ist das pushen zu haesslich?

{
    my @list;

    sub gather (&){
        my $code_ref=shift;
        
        @list=();                          # KORRIGIERT:  danke Matthias W.
        &$code_ref;
        return @list;
    }

    sub take ($) {
        my $elem = shift;
        push @list, $elem;
        return;
    }
}



@x= gather {
    for $c (1..10){   for $b (1..$c){   for $a (1..$b){  if ( $c**2 == $b**2 + $a**2){
        take [$c,$b,$a]
    } } } }
};

print Dumper \@x;




### lazy evaluation ?




{
    my ($a,$b,$c)=(0,0,0);

    sub lazy {
        while ( $c++ < $max ) {
            while ( $b++ < $c ) {
                while ( $a++, $a %= $b ) {
                    return [$c,$b,$a] if $c**2 == $b**2 + $a**2;
                };
                # $a=0; # unnötig
            };
            $b=0;
        }
        $c=0;
        return;
    }
}





while ( $triple = lazy() ) {
    print Dumper $triple;
}
MatthiasW
 2008-10-29 18:09
#115826 #115826
User since
2008-01-27
367 Artikel
BenutzerIn
[default_avatar]
Bei dem gather fehlt aber noch das Resetten von @list, sonst bekommt man ab dem 2. gather auch noch die Ergebnisse der vorherigen.

Ansonsten gibts für List-Comprehensions auch folgendes Modul: CPAN:List::Comprehensions

MfG
perl -E'*==*",s;;%ENV=~m,..$,,$&+42;e,$==f;$"++for+ab..an;@"=qw,u t,,print+chr;sub f{split}say"@{=} me"'
LanX-
 2008-10-29 18:26
#115827 #115827
User since
2008-07-15
1000 Artikel
BenutzerIn

user image
MatthiasW+2008-10-29 17:09:19--
Bei dem gather fehlt aber noch das Resetten von @list, sonst bekommt man ab dem 2. gather auch noch die Ergebnisse der vorherigen.


ja stimmt, aber mir gings darum zu demonstrieren wie einfach man es mit closures realisiert.

KISS!

BTW: Auch kann man es so (noch) NICHT schachteln!

MatthiasW+2008-10-29 17:09:19--
Ansonsten gibts für List-Comprehensions auch folgendes Modul: CPAN:List::Comprehensions


Danke, trotz googeln übersehen ... aber es ist AFAIS zu billig um auf Ronnies Problem angesetzt zu werden, man übergibt fixe Arrayrefs, d.h. $j kann nicht dynamisch bis (1..$i) laufen.

Bei meienm Ansatz kann das ganze semantische Spektrum von Python abgedeckt werden.
<< |< 1 2 >| >> 19 Einträge, 2 Seiten



View all threads created 2008-10-19 15:57.