come enumerare / generare tutti gli alberi binari possibili da N foglie e N-1 nodi?

Naviga le tue risposte
3

Sto cercando di implementare il 24 Game in ansi C. Questo gioco è il seguente:

Per un elenco di quattro numeri dati, prova a trovare una soluzione che coinvolga questi quattro numeri, che, usando addizione (+), sottrazione (-), moltiplicazione (*) e divisione (/) finisca a 24. Ogni numero può apparire solo una volta, ma l'ordine dei numeri potrebbe essere cambiato naturalmente. È possibile usare parentesi per cambiare l'ordine degli operandi (e devi farlo per molte delle soluzioni).

Volevo costruire sopra a questo problema e inventare un gioco M , dove M può essere un numero arbitrario, e puoi dare una lista N di lunghezza arbitraria di valori.

Quello che so:

  • Gli operatori possono essere riutilizzati più volte nella formula. Pertanto, durante l'iterazione degli operatori, posso semplicemente utilizzare i flag per verificare se un determinato operatore debba essere utilizzato in un determinato luogo.
  • I numeri possono essere utilizzati solo una volta. Esistono fantastici tutorial là fuori che spiegano come permutare un array finché tutti i diversi ordini non sono stati esauriti.

Tuttavia, ciò di cui sto ancora avendo problemi, è come decidere le diverse combinazioni di operatori.

Dire che ho una funzione

op(A, B)

Questa funzione non è commutativa, ad es. op (A, B)! = op (B, A). Ora, se ho quattro valori, voglio sapere in che modo ho bisogno di combinare queste funzioni. So che la sequenza di numeri catalani ci dice quante opzioni ci sono. (per quattro numeri, ci sono 5 sequenze ). Questi sono:

  1. op (A, op (B, op (C, D)))
  2. op (op (op (A, B), C), D)
  3. op (op (A, op (B, C), D))
  4. op (A, op (op (B, C), D))
  5. op (op (A, B), op (C, D))

Usando un semplice bitVector con ricorsione riesco a trovare i primi quattro. Ma non il quinto, in cui due nodi condividono lo stesso "livello".

Esiste un modo iterativo per testare tutte queste diverse opzioni?

Oppure, come Ordous giustamente dice:

come enumerare / generare tutti gli alberi binari possibili da N foglie e N-1 nodi?

    
posta Qqwy 28.10.2014 - 16:12
fonte

1 risposta

2

Definisci una funzione ricorsiva che prende una serie di valori e genererà un elenco di tutti gli alberi che vogliamo.

Quando la funzione riceve un solo valore, dovrebbe restituire una lista contenente come unico valore quel valore.

Quando la funzione riceve due valori, dovrebbe restituire una lista contenente come unico elemento l'op di questi due valori in ordine.

Quando la funzione riceve più di due valori, dovrebbe mantenere un elenco da restituire e scorrere tra gli indici tra i membri dell'array. Per ciascun indice tra i membri dell'array, dividere l'array in un array di sinistra e un array di destra in base all'indice. Recurse su questi array, generando l'elenco di alberi per ciascuno. Quindi prendi il prodotto incrociato degli elenchi così generati e aggiungilo all'elenco per tornare.

Il modo in cui funziona è che per qualsiasi array di più di due valori, possiamo suddividerlo in più modi. Per ogni modo di suddividere l'array, c'è almeno un albero possibile sul lato sinistro e almeno un albero possibile sul lato destro. Ogni combinazione di possibili alberi sul lato destro e sinistro è un possibile albero.

Modifica: Ecco qualche pseudo codice (più o meno Java / python): 

List<Tree> getOpTrees(List<Value> values):
    if (length(values) == 1):
        return new List(new IdentityTree(values[0]))
    if (length(values) == 2):
        return new List(new OpTree(values[0], values[1]))
   treeList = new List<Tree>()
   for (index from 1 to length(values)-1):
       leftList, rightList = values.split(index)
   for (leftTree : getOpTrees(leftList)):
   for (rightTree : getOpTrees(rightList)):
        treeList.add(new OpTree(leftTree, rightTree))
return treeList

In realtà, non penso che abbiamo nemmeno bisogno del n = 2 caso base. Se n = 2, avremo sempre solo indice = 1. Quindi dividiamo le liste sinistra e destra, che avranno ciascuna esattamente un elemento. Ognuno di loro restituirà un singolo elenco di elementi contenente l'albero dell'identità del proprio elemento. Quindi l'unica cosa aggiunta a treeList sarà OpTree dei due IdentityTrees.

    
risposta data 28.10.2014 - 16:44
fonte

Leggi altre domande sui tag

Che cos'è un ambiente di database? Relazioni inverse per Aggregati più piccoli / migliori?