Dynamisierung von Code - Grenzen der Machbarkeit? (Allgemeines zu Perl)

[thread]20243[/thread]

Dynamisierung von Code - Grenzen der Machbarkeit?

Tags: perl5 Ähnliche Threads

Leser: 14

Articles: hide open all | hide show old branches

+14 replies
Gast ArthurDent

2017-02-21 23:02
Hallo,

ich zerbreche mir den Kopf über ein Stück generischen Codes. Ich möchte alle Möglichkeiten, in ein n-Tupel die Werte 1 bis k an jede Stelle zu schreiben. generieren.

Wenn ich n weiß, kann ich n for-Schleifen ineinander schachteln. Die Schleifen zählen eben von 1 bis k hoch und fertig. Mein Problem: wie geht das, wenn ich n *nicht* weiß? Selbst mit Rekursion fiel mir nichts Sinnvolles ein...

Beispielannahme: k = 2, n = 3.
Code: (dl )

1 2 3 4 5 6 7

for ($i1 = 0; $i1 <= $k; $i1++) { for ($i2 = 0; $i2 <= $k; $i2++) { for ($i3 = 0; $i3 <= $k; $i3++ { print "hier ist alles zusammen: $i1\t$i2\$i3\t und wird weiter verarbeitet\n"; }; }; };
Dies ist nur ein Ausschnitt aus einem größeren Problem, aber es würde mir enorm weiterhelfen. Danke,
Arthur.
Last edited: 2017-02-21 23:05:43 +0100 (CET)
- thomas38
  
  2017-02-21 23:51
  
  User since
  2012-11-04
  30 Artikel
  BenutzerIn
  
  Wie wäre es rekursiv?
- hlubenow
  
  2017-02-22 02:31
  
  User since
  2009-02-22
  875 Artikel
  BenutzerIn
  
  Dein Output sieht aus wie combinations von Algorithm::Combinatorics, also sowas. In diese Richtung würde ich denken.
  Wenn Du anfängst, das selbst mit einer (oder mehreren?) rekursiven Funktionen schreiben zu wollen, müßtest Du wohl das nachbauen, was das Modul schon sehr gut löst.
- +11 replies
- Muffi
  
  2017-02-22 08:18
  User since
  2012-07-18
  1465 Artikel
  BenutzerIn
  Code (perl): (dl )
  
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
  
  my $n = 3; my $k = 2; sub iterate { my ($curr_n, @values) = @_; for my $curr_k (1..$k) { if ($curr_n == $n) { say join(', ', (@values, $curr_k)); } else { iterate($curr_n +1, (@values, $curr_k)); } } } iterate(1, ());
  
  Last edited: 2017-02-22 08:30:11 +0100 (CET)
  1 + 1 = 10
  - +10 replies
  - hlubenow
    
    2017-02-22 13:44
    
    User since
    2009-02-22
    875 Artikel
    BenutzerIn
    
    Ja, nicht schlecht; sogar ziemlich cool.
    
    Aber auch nicht ganz leicht zu verstehen. Ich wollte z.B. $curr_k in @values mit push() hinzufügen, und dann funktionierte das Ganze nicht mehr, das heißt, @values wuchs auf seltsame Art immer weiter an.
    
    Rekursion ist schon merkwürdig. *kopfkratz*
    - Raubtier
      
      2017-02-22 14:04
      
      User since
      2012-05-04
      1054 Artikel
      BenutzerIn
      
      Wer push macht, muss auch pop machen. Hast du das getan? Sonst wäre es ja kein Wunder, dass @values immer länger wird.
    - Muffi
      
      2017-02-22 14:20
      
      User since
      2012-07-18
      1465 Artikel
      BenutzerIn
      
      Du bist ja hier in einer Schleife.
      Und da willst du:
      @values + aktueller Schleifenzähler.
      Wenn du den jedesmal draufpusht isses klar, dass @values immer länger wird.
      Wenn dann musst du dir ein lokales @values anlegen.
      1 + 1 = 10
    - +7 replies
    - Muffi
      
      2017-02-22 14:31
      
      User since
      2012-07-18
      1465 Artikel
      BenutzerIn
      
      Du kannsts auch ohne Rekursion machen.
      
      Code (perl): (dl )
      
      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
      
      my $n = 3; my $k = 2; my @todo_list = ([ 0, [] ]); while (@todo_list) { my $todo = pop @todo_list; my $local_n = $todo->[0] +1; for my $curr_k (1..$k) { if ($local_n == $n) { say join(', ', @{$todo->[1]}, $curr_k); } else { push @todo_list, [ $local_n, [ @{$todo->[1]}, $curr_k ] ]; } } }
      
      1 + 1 = 10
      - +2 replies
      - hlubenow
        
        2017-02-22 18:38
        
        User since
        2009-02-22
        875 Artikel
        BenutzerIn
        
        Ok. Sehr fortgeschritten, finde ich.
        Ich hab' das für mich mal nach Python übersetzt (da kapier' ich "List of List" besser):
        
        Code (python): (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
        
        #!/usr/bin/python # coding: utf-8 n = 3; k = 2; def toFlatString(todo1, curr_k, callevel, a = None): if a is None: a = [] for i in todo1: if isinstance(i, list): toFlatString(i, None, callevel + 1, a) else: a.append(str(i)) if callevel == 1: a.append(str(curr_k)) return ", ".join(a) todo_list = [[0, []]] while todo_list: todo = todo_list.pop() local_n = todo[0] + 1; for curr_k in range(k + 1): if local_n == n: print toFlatString(todo[1], curr_k, 1) else: todo_list.append([local_n, [todo[1], curr_k]])
        
        (Die Funktion ist nur für das "print", braucht einen nicht zu kümmern: Perl drückt Listen von Listen platt, Python nicht, dafür die Funktion. Egal.)
        
        Man holt sich also eine Liste aus "todo_list" nach "todo" mit pop(). Und dann fügt man wieder eine Liste hinzu, die zwei Elemente enthält. Einmal local_n und dann noch eine Liste (Element 1 von todo). Die dann auch noch irgendwie ein paarmal um curr_k anwächst.
        Und das funktioniert dann auch noch allgemeingültig für verschiedene 'n' und 'k'.
        
        Hmmm. Wirklich genial. Ich gebe zu, daß ich darauf nicht gekommen wäre und schon gar nicht das mit Blick auf diese Kombinationen hätte schreiben können.
        
        Ich dachte noch, vielleicht wäre es einfacher zu verstehen, wenn man das, was "todo" enthält, als Objekt schreiben würde, mit local_n und todo[1] als Attributen? Hat bisher aber noch nicht geklappt.
        
        Ich bin jedenfalls sehr beeindruckt.
        Last edited: 2017-02-22 18:40:45 +0100 (CET)
        
        rosti
        
        2017-02-25 08:51
        
        User since
        2011-03-19
        3194 Artikel
        BenutzerIn
        
        Hi lieber Hauke,
        
        wenn Du ne schöne Idee hast -- lass uns doch mal was mit Perl's API Inline::Python machen ;)
        
        MfG
      - Gast ArthurDent
        
        2017-02-22 21:55
        
        Respekt. Darauf wäre ich nicht gekommen. Tut. Danke! (Aber deswegen fragt man ja...)
        
        Arthur
        Last edited: 2017-02-22 22:03:15 +0100 (CET)
      - +3 replies
      - hlubenow
        
        2017-02-23 13:54
        
        User since
        2009-02-22
        875 Artikel
        BenutzerIn
        
        Hab' mir gerade nochmal die jeweiligen Inhalte von todo_list und todo[1] ausgeben lassen. Skript dazu (im Prinzip Muffis Code von oben):
        
        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
        
        #!/usr/bin/perl use warnings; use strict; use feature 'say'; use Data::Dumper; $Data::Dumper::Indent = 0; my $n = 3; my $k = 2; my @todo_list = ([ 0, [] ]); while (@todo_list) { my $todo = pop @todo_list; my $local_n = $todo->[0] +1; for my $curr_k (1..$k) { if ($local_n == $n) { print "x "; print Dumper(\@todo_list); print " -> "; say join(', ', @{$todo->[1]}, $curr_k); } else { push @todo_list, [ $local_n, [ @{$todo->[1]}, $curr_k ] ]; print Dumper(\@todo_list); print " : "; say join(', ', @{$todo->[1]}, $curr_k); } } }
        
        Ausgabe (nachträglich etwas von Hand eingerückt):
        
        Code: (dl )
        
        1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
        
        $VAR1 = [[1,[1]]]; : 1 $VAR1 = [[1,[1]],[1,[2]]]; : 2 $VAR1 = [[1,[1]],[2,[2,1]]]; : 2, 1 $VAR1 = [[1,[1]],[2,[2,1]],[2,[2,2]]]; : 2, 2 x $VAR1 = [[1,[1]],[2,[2,1]]]; -> 2, 2, 1 x $VAR1 = [[1,[1]],[2,[2,1]]]; -> 2, 2, 2 x $VAR1 = [[1,[1]]]; -> 2, 1, 1 x $VAR1 = [[1,[1]]]; -> 2, 1, 2 $VAR1 = [[2,[1,1]]]; : 1, 1 $VAR1 = [[2,[1,1]],[2,[1,2]]]; : 1, 2 x $VAR1 = [[2,[1,1]]]; -> 1, 2, 1 x $VAR1 = [[2,[1,1]]]; -> 1, 2, 2 x $VAR1 = []; -> 1, 1, 1 x $VAR1 = []; -> 1, 1, 2
        
        Ich hatte mir vorgestellt, todo_list würde sich aufbauen, dann würde ein Ergebnis ausgegeben, und todo_list würde wieder vom Anfang starten (also fast leer).
        Das ist aber nicht der Fall: todo_list baut sich erst eine Weile auf, dann plötzlich werden nacheinander mehrere Ergbnisse ausgegeben (die Zeilen mit 'x') und dann geht es irgendwie weiter.
        Am Ende werden nochmal zwei Werte ausgegeben, obwohl todo_list schon völlig leer ist.
        
        Seltsam.
        
        +2 replies
        
        Muffi
        
        2017-02-23 15:53
        
        User since
        2012-07-18
        1465 Artikel
        BenutzerIn
        
        So kompliziert ist es garnicht.
        
        Lass einfachhalber mal den ersten Wert (also den todo[0]) weg.
        
        dann läufst du die Schleife von 1 - k durch und tust das auf die Todo-Liste.
        Da steht dann z.B.
        * 1
        * 2
        drin.
        
        Dann einen Pop, also die 2 runter.
        
        Dann wieder die Schleife 1 - k.
        
        Also neu auf die Liste drauf:
        
        * 2, 1
        * 2, 2
        
        gesamt steht dann drauf:
        
        * 1
        * 2, 1
        * 2, 2
        
        Dann wieder einen Pop, also 2, 2 runter
        
        Wieder Schleife. Und da jetzt die Anzahl Elemente (oder todo[0], was ich benutzt hab) gleich dem n ist, nicht mehr drauf auf die Liste, sondern ausgeben.
        
        Also:
        
        2, 2, 1 und 2, 2, 2 ausgeben
        
        Liste ist nun:
        
        * 1
        * 2, 1
        
        Und weiter mit Pop, also die 2, 1 runter. Und da es dann wieder n sind ausgeben mit 2, 1, 1 und 2, 1, 2.
        
        Und wieder Pop, also die 1 runter
        
        Schleife 1 - k und drauf:
        
        * 1, 1
        * 1, 2
        
        usw. usw. usw.
        Last edited: 2017-02-23 15:56:37 +0100 (CET)
        1 + 1 = 10
        
        Gast ArthurDent
        
        2017-02-23 22:24
        
        Brutal genial. Jetzt hab ich's auch gecheckt. Wie schon gesagt: DARAUF wäre ich NIE gekommen. Nochmals Danke,
        
        Arthur.
        Last edited: 2017-02-23 22:56:10 +0100 (CET)

View all threads created 2017-02-21 23:02.