Frage zu Tail recursion

[crumble99]

Hallo zusammen,

ich bin gerade bei einem Problem, bei dem ich nicht weiter weiß und mich über eure Hilfe freuen würde. Es ist für mich ein Rekursionsproblem mit folgenden Gesichtspunkte:
Gegeben sei ein numerisches Array der Form

Array
(
    [716] => Array
        (
            [0] => 723
            [1] => 735
            [2] => 746
            [3] => 758
        )

    [723] => Array
        (
            [0] => 716
            [1] => 758
        )

    [735] => Array
        (
            [0] => 716
            [1] => 758
        )

    [746] => Array
        (
            [0] => 716
        )

    [758] => Array
        (
            [0] => 716
            [1] => 723
            [2] => 735
        )
)

Das ganze stellt ein Kombinationsmöglichkeiten mit folgendem Regelwerk dar:
Eine gültige Kombination liegt dann vor, wenn stets ein Schlüssel in seinen inneren (kombinierbaren) Schlüsseln liegt.
Im Bsp heißt das:
716 besitzt die Elemente 723, 735, 746 und 758.
Da die 716 auch in der 723 enthalten ist, stellt dies eine gültige Kombination dar. Mit der 723 ist neben der 716 auch die 758 kombinierbar. Da wiederum die 716 und die 723 Bestandteile von 758 sind, ist
716+723+758 eine gültige Kombination. Ebenfalls gültige Kombinationen sind
716+735+758 sowie
716+746.
Doppelte Einträge sollten nicht dabei sein, d.h. 716+723+758 ist das gleiche wie 723+716+758. Daher ist im oben stehenden Beispiel die Lösungsmenge 3.
Dies versuche ich momentan in PHP in einer rekursiven Funktion niederzuschreiben. Wie bekomme ich nun die Restlisten zusammen mit den erstellten Ergebnislisten rekursiv übertragen?

Ich würde mich riesig über eure Hilfe freuen. Wenn Frage sind, dann immer her damit.

Vielen Dank
Roman

[nikosch]

Dies versuche ich momentan in PHP in einer rekursiven Funktion niederzuschreiben. Wie bekomme ich nun die Restlisten zusammen mit den erstellten Ergebnislisten rekursiv übertragen?

Dann poste den Versuch bitte.

[crumble99]

Eine Recursion ohne weitere Merker verstehe ich ohne weiteres:

function combine($elements)
{
    if(count($elements) == 0) return;
    echo array_shift($elements) . '<br/>';
    combine($elements);

}
$test = array(1,2,3);
combine($test);

Mir ist jedoch unklar, wie ich die stets die verbliebenen Werte und auch die bereits geprüften Werte mitführe. Leider sprengt das meinen Kopf .
Das Rekursionsende ist dann erreicht, wenn kein Element mehr in der zu verarbietenden Liste vorhanden ist.
Die Rekursion sollte besagen, dass der aktuelle key-Wert im Kind-Array enthalten sein muss. Gibt es weitere Kinder, fahre mit denen fort und gib ihnen die bisherigen Elemente (damit eben auch das unterste Element auf ALLE übergeordnete Elemente überprüft werden kann). Aber in der Umsetzung konnte ich bislang keine Ergebnisse aufweisen.

[lstegelitz]

Mir ist jedoch unklar, wie ich die stets die verbliebenen Werte und auch die bereits geprüften Werte mitführe

Als (Referenz-)Parameter für die rekursive Funktion?

[crumble99]

ja, so verfalle ich zumeist im Gedanken. Nur in der Umsetzung haperts dann, da ich immer wieder das Gefühl habe, Werte zu verlieren, die ich später noch brauche...

[lstegelitz]

Ich verstehe das Problem nicht... du benutzt doch schon einen Parameter, wo ist die Schwierigkeit einen weiteren hinzuzufügen?

$elements enthält die Daten. Mit jedem Rekursionsdurchlauf verringerst du die Anzahl der Elemente und rufst die Funktion erneut mit der reduzierten Menge auf.
Genauso kannst du auch ein zweites Array durchschleifen, in das du die Dinge ablegst, die bereits verarbeitet wurden. Das Ding wächst mit jeder Rekursion.

[erc]

Entweder versteh ich das Problem falsch, oder das hat nix mit Rekursion zu tun. 2 Schleifen und eine Funktion zum Suchen tuns auch.

$result = array();

foreach($ganzesding AS $id => $inner_ids) {
   $valid_inner_ids = array();
   foreach($inner_ids AS $inner_id) {
       if(prüfe_ob_id_in_inner_id_enthalten_ist($id, $inner_id)) {
           $valid_inner_ids[] = $inner_id;
       }
   }
   if($valid_inner_ids) {
       $result[] = $valid_inner_ids
   }
}

var_dump($result);

//--------------

function prüfe_ob_inner_id_in_id_enthalten_ist($id, $inner_id) {
     global $ganzesding; //hat keiner gesehen, mach ne klasse draus, übergebs oder keine ahung

     $key = array_search($inner_id, $ganzesding);
     if($key === false) return false;

     $key = array_search($id, $ganzesding[$inner_id]);

     return $key !== false;
} 

Kann man natürlich auch rekusiv machen, man kann sich aber auch selbst ins Knie schießen.

[crumble99]

@erc: Das klappt leider nicht für beliebige Tiefen.
Hier noch einmal der Arbeitsprozess:
Definition der Ausgangsdaten:

$a716 = array(723,735,746,758);
$a723 = array(716,758);
$a735 = array(716,758);
$a746 = array(716);
$a758 = array(716,723,735);

$a[716] = $a716;
$a[723] = $a723;
$a[735] = $a735;
$a[746] = $a746;
$a[758] = $a758;

0) für jedes Element in $a prüfe kombinierbarkeit
1) 716 ist mit 723, 735, 746 und 758 injektiv kombinierbar. Nimm nun jedes Element, zunächst 723
2) gehe in $a[723], prüfe, ob 716 gesetzt ist (bijektiv kombinierbar). wenn ja, ist 716<->723 eine Kombination. andernfalls brich ab
3) gibt es weitere elemente in $a[723]? (ja, 758 )
4) gehe in $a[758], prüfe ob 716 und 723 existieren. wenn ja, ist 716<->723<->758 eine Kombination. andernfalls brich mit Ergebnis 716<->723 ab
5) gibts es weitere elemente in $a[723]? nein -> eine stufe zurück
6) gibt es weitere Elemente in $a[716]? ja, 735
... fahre nun mit den anderen fort.
nach $a716 geht es mit $a[723] weiter. Da die 723 wiederum mit der 716 und der 758 kominierbar ist, wird dies nicht erneut in die Ergebnismenge aufgenommen, so dass am Schluss nur besagte 3 Kombinationen übrig bleiben.

Mein bisherige Ansatz ist folgender:

$a716 = array(723,735,746,758);
$a723 = array(716,758);
$a735 = array(716,758);
$a746 = array(716);
$a758 = array(716,723,735);

$a[716] = $a716;
$a[723] = $a723;
$a[735] = $a735;
$a[746] = $a746;
$a[758] = $a758;

$res = array();
foreach($a as $key => $values) {
    combine($key, $values, $res);
}

function combine($k, $v, &$res)
{
    if(in_array($k, $v)) {
        $res[$k][] = $k;
        if(count($s = array_slice($v, 1)) > 0) {
            combine($k, $s, $res);
        }
    }
}

Das macht jedoch noch nicht was es soll und daher brauche dazu bitte eure Hilfe.

Viele Grüße
Roman

[ChristianK]

Entweder versteh ich das Problem falsch, oder das hat nix mit Rekursion zu tun. 2 Schleifen und eine Funktion zum Suchen tuns auch.
[...]

Jede Funktion lässt sich iterativ oder rekursiv darstellen.


@TE: Was ist denn der Output der Funktion bzw. wo happert es denn genau?

[jspit]

Was soll das hier bringen nachdem die Diskussion hier schon im Gange war?

[nikosch]

Bitte beachten: Anmerkungen zu Crosspostings

[MOD: Thread geschlossen]