Ankündigung

Einklappen
Keine Ankündigung bisher.

[Erledigt] Kombination Buchstaben

Einklappen

Neue Werbung 2019

Einklappen
X
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • [Erledigt] Kombination Buchstaben

    Hallöchen,

    ich hätte eine Frage an Euch zur Kombination und Zusammensetzung verschiedener Buchstaben (mal grob formuliert). Vielleicht mag sich ja jemand reindenken und mir helfen

    Also angenommen ich habe eine Erbsenpflanze a la Mendel.

    Sagen wir, es gibt folgende Merkmale:
    Blüte: Rr (= rot), RR (= rot), rr (= weiß)
    Frucht: Gg (= gelbgrün), GG (= gelb), gg (= grün)
    Form: Ff (= runzelig), FF (= runzelig), ff ( = glatt)

    Nun habe ich per POST die Merkmale der zwei Pflanzen bekommen und würde gerne die F1-Generation ausrechnen lassen mit allen möglichen Kombis.

    z.B. Pflanze1: RrGGff, Pflanze2: rrGGFf
    gäbe folgende Kombinationen:
    RrGGff
    rrGGff
    RrGGFf
    rrGGFf

    Es würde reichen, die "einzigartigen" Kombis, also nicht unbedingt, wenn eins mehrmals rauskommt, zu bekommen (falls das besser ginge).

    Habe schon daran gedacht, die Paare, also Rr mit str_split aufzuspalten in R und r um sie besser zu kombinieren. Aber jetzt bin ich gerade etwas ratlos in der Kombination der Pflanzen und vor allem des kompletten "Codes", also Blüte+Frucht+Form...

    Den "Ergebnissen" liegen in einer Datenbank die dazugehörigen "Ausgabenamen" bereit, also dass z.B. bei rrGGff später herauskommt: "Weiße Blüte mit gelber, glatter Frucht".

    LG


  • #2
    F1-Generation ist was ? Das was du da als Beispiel zeigst ist eine Kombinationsliste die auf Gemeinsamkeiten beider String matched.

    Grundsätzlich könntest du hingehen und beide Strings splitten ( wie du schon beschreibst ) und ein intersect aus beiden erzeugen das dir die Gemeinsamkeiten ( mit Schlüsselpositionen ) zurückgibt. Damit könntest du dann deine Kombinationen filtern auf eben diese beiden Gemeinsamkeiten.

    [man]str_split[/man], [man]array_intersect[/man] und [man]array_filter[/man] genügen da wohl.

    Sind deine Kombinationen wirklich so steif wie oben beschrieben oder sollen die sich irgendwann nochmal verändern ? Technisch gesehen kannst du deine Teilchen-DNA eher zu einer Liste legen die mit Zuständen statt mit buchstaben arbeitet

    Code:
    | blüte1 | blüte2 | frucht1 | frucht2 | form1 | form 2 |
    +--------+--------+---------+---------+-------+--------+
    | 1      | 0      | 1       | 1       | 0     | 0      | RrGGff
    [URL="https://gitter.im/php-de/chat?utm_source=share-link&utm_medium=link&utm_campaign=share-link"]PHP.de Gitter.im Chat[/URL] - [URL="https://raindrop.io/user/32178"]Meine öffentlichen Bookmarks[/URL] ← Ich habe dir geholfen ? [B][URL="https://www.amazon.de/gp/wishlist/348FHGUZWTNL0"]Beschenk mich[/URL][/B].

    Kommentar


    • #3
      Schau auch mal hier: http://php-de.github.io/jumpto/kombinatorik-loesungen/
      Debugging: Finde DEINE Fehler selbst! | Gegen Probleme beim E-Mail-Versand | Sicheres Passwort-Hashing | Includes niemals ohne __DIR__
      PHP.de Wissenssammlung | Kein Support per PN

      Kommentar


      • #4
        Brauchte etwas zum wachwerden..

        Der folgende Code nutzt die interne Darstellung eines Integer als Modell für die Kombinationsmöglichkeiten:
        PHP-Code:
        $Pflanze1 'RrGGff';
        $Pflanze2 'rrGGFf';

        $sp = array(
          
        str_split($Pflanze1,2),
          
        str_split($Pflanze2,2),
        );

        $splitCount count($sp[0]);  //Anzahl Merkmale
        $n pow(2,$splitCount);

        $combi = array();
        for(
        $i=0;$i<$n;$i++){
            
        $element '';
            for(
        $j=0$j<$splitCount$j++) {
                
        $element .= $sp[$i>>$j&1][$j];
            }
            
        $combi[] = $element;
        }

        //doppelte Kombinationen entfernen
        $combi array_values(array_unique($combi));

        var_dump($combi); 
        Es werden alle möglichen Kombinationen inklusive der Doppelten berechnet und dann erst gefiltert.
        PHP-Klassen auf github

        Kommentar


        • #5
          Übrigens, die F1-Generation ist die erste Filialgeneration.

          Kommentar


          • #6
            Guten morgen allerseits ^^ erstmal dickes Danke

            Dann noch ein kleines Sorry, ich war beim Posten so verplant, weil schon recht lang wach, dass ich nicht gesehen hab, dass ich in "Fortgeschrittene" gepostet hab, wollte eigentlich in "Einsteiger" posten, weil ich nicht alle Voraussetzungen für Fortgeschritten erfülle :S @Mod: kannst Du das verschieben? :$

            So, dann stelle ich mich erst mal den offenen Fragen ^^

            F1-Generation ist was ?
            Ja, wie alxy geschrieben hat, einfach Vater x Mutter ^^ so gesehen. Dann kann man die ganzen aus F1 wieder untereinander kreuzen und kommt auf die F2 usw...

            Sind deine Kombinationen wirklich so steif wie oben beschrieben oder sollen die sich irgendwann nochmal verändern ?
            Ja, es ist so, dass ich die Merkmale der "Eltern" als Parameter übermittelt bekomme (wobei, wie man oben sieht, rot auch RR und Rr sein kann). Dabei hab ich dann manchmal auch ein "unbekannt" im Gencode, also z.B. Ru falls man nur rot weiß, nicht aber den zweiten Buchstaben. Die zwei Eltern werden dann gekreuzt und alle "uniquen" (sag ich mal so) Kinder werden mit Gencode und "Name" gelistet (der Name wird aus einer DB abgerufen).

            Es gibt insgesamt übrigens 6 Merkmale, die jeweils die Möglichkeiten kleinklein Großklein GroßGroß oder unbekannt haben können. Es werden aber nur die "entscheidenden" Merkmale genommen (also bei einer Pflanze, die wenn sie rot wäre, auch Streifen hätte, aber weiß ist, kann das mit den Streifen vernachlässigt werden).

            @hausl: das mit den Kombinatorik-Lösungen hilft mir grad nur bedingt, das hab ich in der Vorlesung schon gehasst -.- muss mal schauen, obs auch ohne geht :'D ansonsten hab ich ja hier den Link

            @jspit: wow, das sieht sehr gut aus habs probiert, aber es kommen nicht alle Kombis so wie es sein sollte.. Mal ein Bsp:

            für $Pflanze1 = 'RrFf'; $Pflanze2 = 'Rrff';

            müssten ja folgende Kombis rauskommen:
            RRFf
            RrFf
            RRff
            Rrff
            rrFf
            rrff

            hab mal "per Hand" gekreuzt, so kann man das machen (zwei Varianten):

            (das blaue sind die einzigartigen, das orangene die doppelten, nur zur Orientierung)

            Dein Code bringt mir allerdings nur:

            array(2) { [0] => string(4) "RrFf" [1] => string(4) "Rrff" }


            Werd mich mal versuchen, in die anderen Vorschläge reinzudenken, falls man damit so was hinkriegen kann ^^

            LG


            Edit: die Anzahl der möglichen Ergebnisse erhält man eher wenn man die Codes nicht auf Merkmale splittet, sondern auf die einzelnen "Gene":

            PHP-Code:
            $sp = array(
            str_split($Pflanze1,1),
            str_split($Pflanze2,1),
                );

                
            $splitCount count($sp[0]);  //Anzahl Gene
                
            $n pow(2,$splitCount); 
            So kriegt man zwar 16 Ergebnisse, aber nicht die "richtigen" :'D allerdings kann ich das $combi, wie sie jspit geschrieben hat nicht umschreiben, sodass es klappt :/

            Kommentar


            • #7
              Da ist wohl was Grundlegendes nicht zu mir rübergekommen.
              Liefert denn
              $Pflanze1 = 'Rr'; $Pflanze2 = 'Rr';
              mehrere Kombinationen?
              PHP-Klassen auf github

              Kommentar


              • #8
                Naja, so wie du es geschrieben hast, kommt als Ergebnis heraus:

                array(1) { [0] => string(2) "Rr" }

                allerdings müsste ja theoretisch RR, Rr, rr herauskommen (genau genommen: RR, Rr, Rr, rr)..

                kriegt man das hin, dass man jedes mit jedem kombiniert? o:

                LG & danke für die Hilfe ^-^

                Kommentar


                • #9
                  Ich habe keine Ahnung wie genau die Kreuzung funktioniert? Wonach wählst du die Spalten- und Zeilen-Bezeichner aus in deiner Matrix? (oberes Bild)

                  Also konkret, wie komme ich von 'RrFf' und 'Rrff' zu der gezeigten Tabelle. Wenn man das nämlich weiß, kann man einfach alle Kombinationen daraus berechnen (vermute ich mal).

                  Kommentar


                  • #10
                    @alxy: hmm, die Tabelle hab ich ja bloß zur Veranschaulichung geschrieben. Das ist ne ganz normale Verkreuzungstabelle. So macht man sich das Schema:

                    man nimmt RrFf als Elter. Dieses gibt bei der Kreuzung von jedem Merkmal ein Gen an das "Kind" weiter. Also schreibt man sich alle möglichen "Gameten" auf.

                    Es geht bei RrFf also das R mit dem F, das R mit dem f, das r mit dem F und das r mit dem f.
                    RF, Rf, rF, rf -> das ist die erste Zeile der ersten Tabelle.
                    für Rrff gibt es:
                    Rf, Rf, rf, rf -> das ist die erste Spalte der ersten Tabelle.

                    Dazwischen schreibt man einfach die Buchstaben wieder zusammen -> die 16 Ergebnisse.

                    Dieses Muster in der zweiten Tabelle kann man z.B. in Excel schreiben, wenn man möchte, aber das kann man ja schlecht umschreiben...

                    Hoffe, das ist verständlich? :S

                    LG

                    PS: vllt hilft dieses Bildchen zur Veranschaulichung

                    Kommentar


                    • #11
                      Keine Ahnung, ob das so richtig oder schlau ist:

                      (Edit: Hatte beim Copy&Paste vergessen, die erste Zeile in der Tabelle anzupassen. Stimmt jetzt.)

                      PHP-Code:
                      <?php

                      /**
                       * rRfF => RrFf
                       *
                       * @param string $plant
                       * @return string
                       */
                      function reorder($plant)
                      {
                          
                      $length strlen($plant);

                          
                      // For every two characters
                          
                      for ($i 0$i $length$i += 2) {
                              
                      // Characters are equal
                              
                      if ($plant[$i] === $plant[$i 1]) {
                                  continue;
                              }

                              
                      // Second character is lowercase
                              
                      if ($plant[$i 1] === strtolower($plant[$i 1])) {
                                  continue;
                              }

                              
                      // Otherwise switch
                              
                      $tmp $plant[$i];
                              
                      $plant[$i] = $plant[$i 1];
                              
                      $plant[$i 1] = $tmp;
                          }

                          return 
                      $plant;
                      }

                      /**
                       * The code doesn't change input strings into arrays, but the strings will be
                       * interpreted like this:
                       *
                       *     p1 = 'RrFf' = [[R,r], [F,f]]
                       *     p2 = 'Rrff' = [[R,r], [f,f]]
                       *
                       * The algorithm creates a bit field for every possible combination. Those bits
                       * will then be mapped sequentially to either the first (if 0) or the second
                       * (if 1) entry of the first tuple in the p1 set ([R,r]), then of the first
                       * tuple in the p2 set ([R,r]), then of the second tuple in the p1 set ([F,f]),
                       * and so on. See the following table for details.
                       *
                       *     abcd     k  a      k  b     k+1 c     k+1 d
                       *     --------------------------------------------------
                       *     0000  p1[0][0]  p2[0][0]  p1[1][0]  p2[1][0]  RRFf
                       *     ...
                       *     0110  p1 " [0]  p2 " [1]  p1 " [1]  p2 " [0]  Rrff
                       *     ...
                       *     1111  p1 " [1]  p2 " [1]  p1 " [1]  p2 " [1]  rrff
                       *
                       * @param string $plant1
                       * @param string $plant2
                       * @return array
                       */
                      function cross($plant1$plant2)
                      {
                          
                      $fields       strlen($plant1);
                          
                      $combinations pow(2$fields);

                          
                      $tmp = array();

                          for (
                      $i 0$i $combinations$i++) {
                              
                      $pattern sprintf('%0' $fields 'b'$i);

                              
                      $res '';

                              for (
                      $j 0$j $fields$j++) {
                                  
                      // $k = 0, 2, 4, ...
                                  
                      $k = ($j === 0) ? $j $j 1;

                                  if (
                      $pattern[$j] === '1') {
                                      
                      $k++;
                                  }

                                  
                      $res .= (($j === 0) ? $plant1[$k] : $plant2[$k]);
                              }

                              
                      $tmp[reorder($res)] = true;
                          }

                          return 
                      array_keys($tmp);
                      }



                      var_dump(cross('RrFf'  'Rrff'));
                          
                      // "RRFf", "RRff", "RrFf", "Rrff", "rrFf", "rrff"

                      var_dump(cross('Rr'    'Rr'));
                          
                      // "RR", "Rr", "rr"

                      var_dump(cross('RrGGff''rrGGFf'));
                          
                      // "RrGGFf", "RrGGff", "rrGGFf", "rrGGff"

                      Kommentar


                      • #12
                        @ mermshaus: das sieht schon mal biologisch sehr richtig aus ^^ jetzt müsste ich nachher nur mal schauen, ob man das einfach auf 6 Merkmale erweitern kann, also so wie AaBbCcDDeeFF... Nun ruft die Arbeit erst mal :'D

                        LG

                        Kommentar


                        • #13
                          Sechs sollten noch kein Problem sein. So ab etwa zehn Merkmalen wird es halt spürbar langsam und dann auch praktisch sofort zu langsam.

                          Mein Ansatz behandelt zudem kein „u“, aber dazu fehlen wohl im Zweifel auch noch Informationen, was damit geschehen soll.

                          Kommentar


                          • #14
                            Ich habe so was vor einiger Zeit glaube ich auch mal allgemeiner programmiert (ohne den sprintf-/Binär-„Hack“):

                            PHP-Code:
                            <?php

                            function getNthPermutation(array $dimensions$n)
                            {
                                
                            $dimIndizes array_keys($dimensions);
                                
                            $retVector = array();

                                foreach (
                            $dimIndizes as $key) {
                                    
                            $retVector[$key] = null;
                                }

                                
                            $dimCount count($dimensions);
                                
                            $dimLenghts = array();

                                foreach (
                            $dimensions as $d) {
                                    
                            $dimLenghts[] = count($d);
                                }

                                
                            $permutations array_product($dimLenghts);

                                
                            // Normalize $n to be in [0, $permutations)

                                
                            while ($n 0) {
                                    
                            $n += $permutations;
                                }

                                while (
                            $n >= $permutations) {
                                    
                            $n -= $permutations;
                                }

                                
                            $f 1;

                                for (
                            $i $dimCount 1$i >= 0$i--) {
                                    
                            $key $dimIndizes[$i];

                                    
                            $index = (($n $n $f) / $f) % $dimLenghts[$i];

                                    
                            $retVector[$key] = $dimensions[$key][$index];

                                    
                            $f *= $dimLenghts[$i];
                                }

                                return 
                            $retVector;
                            }


                            error_reporting(-1);
                            ini_set('display_errors'1);

                            $input = array(
                                
                            'typA' => array(
                                    
                            123
                                
                            ),
                                
                            'typB' => array(
                                    
                            'A''B''C''D'
                                
                            ),
                                
                            'typC' => array(
                                    
                            'Grün''Blau'
                                
                            )
                            );

                            $format = function ($a) {
                                
                            $s '';
                                foreach (
                            $a as $k => $v) {
                                    
                            $s .= sprintf("%s : %s\t"$k$v);
                                }
                                
                            $s rtrim($s);
                                return 
                            $s;
                            };

                            for (
                            $i = -24$i <= 24$i++) {
                                
                            printf("%s\t%s\n"$i$format(getNthPermutation($input$i)));
                            }
                            - http://phpforum.de/forum/showthread.php?t=271262

                            Die Funktion nimmt eine Anzahl n an Arrays und einen Index i als Eingabe und liefert ein Array der Größe n mit der i-ten Kombination von je einem Element aus jedem der Eingabe-Arrays zurück.

                            PHP-Code:
                            <?php

                            // Unverändert, wie oben
                            function reorder($plant)
                            {
                                
                            $length strlen($plant);

                                
                            // For every two characters
                                
                            for ($i 0$i $length$i += 2) {
                                    
                            // Characters are equal
                                    
                            if ($plant[$i] === $plant[$i 1]) {
                                        continue;
                                    }

                                    
                            // Second character is lowercase
                                    
                            if ($plant[$i 1] === strtolower($plant[$i 1])) {
                                        continue;
                                    }

                                    
                            // Otherwise switch
                                    
                            $tmp $plant[$i];
                                    
                            $plant[$i] = $plant[$i 1];
                                    
                            $plant[$i 1] = $tmp;
                                }

                                return 
                            $plant;
                            }

                            // Unverändert, wie oben
                            function getNthPermutation(array $dimensions$n)
                            {
                                
                            $dimIndizes array_keys($dimensions);
                                
                            $retVector = array();

                                foreach (
                            $dimIndizes as $key) {
                                    
                            $retVector[$key] = null;
                                }

                                
                            $dimCount count($dimensions);
                                
                            $dimLenghts = array();

                                foreach (
                            $dimensions as $d) {
                                    
                            $dimLenghts[] = count($d);
                                }

                                
                            $permutations array_product($dimLenghts);

                                
                            // Normalize $n to be in [0, $permutations)

                                
                            while ($n 0) {
                                    
                            $n += $permutations;
                                }

                                while (
                            $n >= $permutations) {
                                    
                            $n -= $permutations;
                                }

                                
                            $f 1;

                                for (
                            $i $dimCount 1$i >= 0$i--) {
                                    
                            $key $dimIndizes[$i];

                                    
                            $index = (($n $n $f) / $f) % $dimLenghts[$i];

                                    
                            $retVector[$key] = $dimensions[$key][$index];

                                    
                            $f *= $dimLenghts[$i];
                                }

                                return 
                            $retVector;
                            }


                            error_reporting(-1);
                            ini_set('display_errors'1);

                            // RrFf X Rrff

                            $input = array(
                                array(
                            'R''r'),
                                                array(
                            'R''r'),
                                array(
                            'F''f'),
                                                array(
                            'f''f'),
                            );

                            $keys = array();

                            for (
                            $i 0$i 16$i++) {
                                
                            $tmp reorder(implode(''getNthPermutation($input$i)));
                                
                            $keys[$tmp] = true;
                            }

                            var_dump(array_keys($keys));
                                
                            // "RRFf", "RRff", "RrFf", "Rrff", "rrFf", "rrff"
                            Ich sage dazu aber mal vorsichtig: Keine Gewähr.

                            Kommentar


                            • #15
                              @ mermshaus:

                              Danke! Das hat super funktioniert, habe deinen oberen Code genommen und auf meine Bedürfnisse zurechtgeschnitten :'D das scheint echt zu funktionieren, so weit ich es gesehen hab, müsste alles klappen

                              Super, danke für die schnelle Hilfe

                              LG

                              PS: das mit dem "U" hat sich erledigt, habe es umgeschrieben, dass das nicht mehr nötig ist ^^

                              Kommentar

                              Lädt...
                              X