PHP funkcja rekurencyjna

Mam tablicę stanów jaką może przyjmować tekst jaki przepływa przez mój system

$stany = array(
        1  => array(2),         //u admina;  sprawdza nowo wysłany wniosek
        2  => array(11,12),     //u pisarza; sprawdza nowo otrzymane zlecenie
        11 => array(12),        //u klienta; wyrażenie zgody na wydłużenie czasu przedłużenia
        12 => array(3,11),      //u pisarza; tekst jest właśnie pisany
        3  => array(4),         //u admina;  sprawdza krytyczne wyrazy w tekście1
        4  => array(5),         //u klienta; sprawdza otrzymany tekst
        5  => array(6),         //u admina;  odebrał od klienta zgłoszone poprawki do tekstu
        6  => array(7),         //u pisarza; dostaje poprawki od klienta (czyt. pisze tekst2)
        7  => array(13),        //u admina;  sprawdza tekst2
        13 => array(10),        //u klienta; dostaje tekst2
        10 => null,
    );

Chciałbym napisać funkcję, która przyjmowałaby (int)$argument aktualnego stanu i aby "wypluła" przypuszczalne stany jakie mogą nastąpić po tym stanie.

Czyli:
funkcja(2) powinna zwrócić tablicę z wpisami Array(11,12,3,4,5,6,7,13,10)
funkcja(11) => Array(12,3,11,4,5,6,7,13,10)
funkcja(6) => Array(7,13,10)

Próbowałem to zrobić ale albo algorytm nie kończy swojego działania, albo przepełnienie pamięci następuje :(

Odpowiedz na pytanie

1

Odpowiedzi: 3

  • 2 lata, 2 miesiące temu
    autor: newton

    4

    Tabelkę ze stanami wejściowymi ($stany z pytania) należy przekazać jako $deps:

    function possibleStates($from, $deps, $states = array())
{
        if($deps[$from])
        foreach($deps[$from] as $nextState)
        {
                if(!in_array($nextState, $states))
                {
                        $states[] = $nextState;
                        $states = possibleStates($nextState, $deps, $states);
                }
        }
        return $states;
}

var_dump(possibleStates(11, $stany));

  • 2 lata, 2 miesiące temu
    autor: Manveru

    2

    Odpowiedź w formie pseudokodu:

    funkcja zwróć_możliwe_stany(stan_wejściowy)
{
    utwórz zbiór pusty;
    dodaj do zbioru te stany, które wskazuje tablica dla stanu wejściowego;
    pętla
    {
        dla każdego elementu w zbiorze pobierz z tablicy nowe stany
        {
            dla każdego nowego stanu
            {
                sprawdź czy nowy stan jest już w zbiorze
                {
                    jeśli nie:
                        dodaj do zbioru i podnieś flagę;
                    jeśli tak:
                        przejdź do następnego;
                }
            }
        }
        jeśli flaga podniesiona przerwij pętlę;
        opuść flagę;
    }
    zwróć zbiór;
}

    W ten sposób unikniesz rekurencji. Mam nadzieję, że nie rąbnąłem się w logice, ale powinno bezpiecznie się kończyć.

    O ile mnie pamięć nie myli, PHP zawiera funkcje do traktowania tablicy (ang. array) jak zbioru (ang. set).

  • 2 lata, 2 miesiące temu
    autor: skarat

    0

    Nie rekurencja i w zasadzie zadanie już masz rozwiązane, ale może przyda Ci się takie podejście:

       function mozliweStany( $aWszystkieStany, $iStanWejsciowy ){

    $bKolejneStany = false;
    $aKolejneStany = array();
    foreach( $aWszystkieStany as $klucz => $pozycja ){

        if( $klucz == $iStanWejsciowy ){
            $bKolejneStany = true;
        }
        if( $bKolejneStany && $pozycja !== null ){
            $aKolejneStany = array_merge( $aKolejneStany, $pozycja );
            if( count( $pozycja ) > 1 ){
                print_r( count( $pozycja ) . $pozycja[ 1 ] );
                for( $i = 1, $iCount = count( $pozycja ); $i < $iCount; $i++){
                    $aKolejneStany = array_merge( $aKolejneStany, $aWszystkieStany[ $pozycja[$i] ] );                   
                }
            }
        }
    }
    return array_unique( $aKolejneStany );
}

    Zaletą rozwiązania jest fakt, że używasz funkcji PHP zoptymalizowanych do obsługi tablic oraz to, że nie ma rekurencji ;-)

Zaloguj się, aby dodać swoją odpowiedź