algoritmo per estrarre "possibilità" da un albero

Soluzione ricorsiva come segue. Essenzialmente devi percorrere l'albero in primo piano in profondità, restituire liste di nodi e infine costruire un nuovo albero.

• Da un nodo foglia, return self.
• Da un nodo variante, restituisce un elenco formato concatenando i nodi restituiti da ciascun figlio, con autoinserito in primo piano.
• Al livello più alto, forma una serie di tuple che sono il prodotto cartesiano di tutti i suoi nodi figli. Quindi, per ogni tupla, crea un albero che ha sé come testa e una tupla come ogni gruppo di rami; ritorna la lista degli alberi.

Sembra complicato, ma probabilmente è meno di 50 righe di Ruby. Non sono ancora convinto che la domanda sia ben formata, ma questo algoritmo produrrà l'output specificato.

Sarei tentato di pensare che ci siano almeno un paio di modi in cui potresti descrivere la soluzione qui:

1. Set di nodi foglia - Poiché tutti i genitori saranno inclusi in ogni risultato, potrebbe essere più semplice visualizzare un elenco di liste in cui si sta semplicemente selezionando ogni possibile configurazione di valori. Guardando l'esempio di ((Small box, heavy box),(Standard, Express)) genererebbe le possibilità che potrebbero essere fatte con forza bruta se non altro: ((Small box, Standard), (Small box, Express), (Heavy box, Standard), (Heavy box, Express))

2. Guardando avanti - Se ci sono più livelli da percorrere, allora tutti i nodi verranno aggiunti, ma se c'è solo un altro strato da percorrere, allora ogni possibilità deve essere aggiunta. L'idea qui è di considerare come Packaging e Delivery sono in ogni albero, ma i nodi foglia sono scelti in modo univoco. Questo potrebbe essere fatto ricorsivamente guardando più in basso lungo l'albero poiché ci sono alcuni casi speciali da gestire come un albero vuoto e un singolo nodo per dare un paio di esempi. Se ci sono un paio di livelli o più, puoi usare l'idea del futuro.

Rappresenta il tuo problema come una grammatica:

product: packaging delivery
packaging: heavy-box | small-box
delivery: standard | express

È facile estendere a un terzo livello:

product: packaging delivery
packaging: heavy-box | small-box
delivery: standard | express
heavy-box: small | large

Con il tuo problema in BNF, tutto ciò di cui hai bisogno è un programma in grado di generare tutte le possibili stringhe accettate da questa grammatica.

Per cominciare, qui c'è una funzione per contare fino alla quantità totale di possibili nuovi alberi. Input è il nodo nella radice dell'albero.

function CountPossibilities(node)

    _result = 0

    if node.isvariant then

        _result = 0

        for each _child in node.childnodes

            _result += CountPossibilities(_child)

        next

    else

        _result = 1

        for each _child in node.childnodes

            _result *= CountPossibilities(_child)

        next

    end     

    return _result

end function