[Erledigt] Kombination Buchstaben

[IWKYS]

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

[tr0y]

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

| blüte1 | blüte2 | frucht1 | frucht2 | form1 | form 2 |
+--------+--------+---------+---------+-------+--------+
| 1      | 0      | 1       | 1       | 0     | 0      | RrGGff

[hausl]

Schau auch mal hier: http://php-de.github.io/jumpto/kombinatorik-loesungen/

[jspit]

Brauchte etwas zum wachwerden..

Der folgende Code nutzt die interne Darstellung eines Integer als Modell für die Kombinationsmöglichkeiten:

$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.

[alxy]

Übrigens, die F1-Generation ist die erste Filialgeneration.

[IWKYS]

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":

$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 :/

[jspit]

Da ist wohl was Grundlegendes nicht zu mir rübergekommen.
Liefert denn
$Pflanze1 = 'Rr'; $Pflanze2 = 'Rr';
mehrere Kombinationen?

[IWKYS]

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 ^-^

[alxy]

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).

[IWKYS]

@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

[mermshaus]

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

/**
 * 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 % 2 === 0) ? $j : $j - 1;

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

            $res .= (($j % 2 === 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"

[IWKYS]

@ 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

[mermshaus]

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.

[mermshaus]

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

<?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(
        1, 2, 3
    ),
    '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

// 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.

[IWKYS]

@ 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 ^^