Generazione di combinazioni algoritmicamente

Question

Generazione di combinazioni algoritmicamente

#1 da (2 voti)
#2 da (0 voti)

2

Supponiamo di avere una piramide n-alta di numeri come:

Come posso percorrere algoritmicamente ogni possibile percorso dalla cima della piramide alla fine?

Per spiegarti meglio, lascia che rappresenti la piramide in questo modo:

1 2 3 4 5
-----------
1         | a
5 8       | b
2 5 4     | c
8 9 3 1   | d
2 8 3 7 2 | e

Ad esempio:

        On the path | a b c d e (Path)
       -------------|------------------
Path 1:  1 5 2 8 2  | 1 1 1 1 1
Path 2:  1 5 2 8 8  | 1 1 1 1 2
Path 3:  1 5 2 9 8  | 1 1 1 2 2
Path 4:  1 5 2 9 3  | 1 1 1 2 3
...
Path m:  1 8 4 1 2  | 1 2 3 4 5

Dove m è il numero totale di percorsi.

Capisco che il problema può essere ridotto a generare semplicemente tutti i possibili percorsi denotati nella seconda colonna della tabella, e potrei arrivare abbastanza facilmente con un algoritmo per generare quelli per un 5-alto (o qualsiasi altro fisso alto) piramide, ma non riesco a trovare una soluzione generale.

L'algoritmo non può essere ricorsivo, per il semplice motivo che ho già risolto il problema in modo ricorsivo e sono interessato a una soluzione non ricorsiva per ottenere una visione completa del problema.

algorithms

posta Riccardo Bestetti 04.10.2015 - 22:06

fonte

2 risposte

Leggi altre domande sui tag algorithms

Come evitare la duplicazione del codice o le modifiche in cascata e il principale refactoring nel livello della business logic? query SQL nei test di integrazione

score 2 · Answer 1

Se inizi nella parte superiore del triangolo ci sono solo 2 scelte per continuare il percorso - a sinistra oa destra. Se hai scelto sinistra, ci sono solo 2 scelte per continuare il percorso - a sinistra oa destra. Se hai scelto bene, allora c'è solo ...

Codifichiamo la decisione "sinistra o destra" ad ogni livello come 1 bit, dove 0 = sinistra e 1 = destra. Se ci sono 5 livelli puoi codificare un percorso come 4 bit. Se ci sono N livelli è possibile codificare un percorso come (N - 1) bit. Il numero di percorsi è 1 < < (N - 1).

Ora pensiamo alla riga in basso. Se scegli sempre "left", allora sarebbe il percorso 0000b, che non ha bit impostati, e finisci con il numero 0 nella riga in basso. Se scegli sempre "right", allora sarebbe il percorso 1111b, che ha 4 bit impostati, e finisci con il 4 ° numero nella riga in basso. Se si alternano (a sinistra, a destra, a sinistra, a destra) il percorso sarà 0101b, che ha 2 bit impostati e si arriverà al 2 ° numero nella riga in basso. Se si alterna il modo opposto (a destra, a sinistra, a destra, a sinistra) sarà il percorso 1010b, che ha 2 bit impostati, e si arriva al 2 ° numero nella riga inferiore. La posizione del numero nella riga inferiore dipende dal numero di bit impostati nel percorso.

Ora pensa alla penultima riga - è uguale all'ultima riga, tranne che ignori l'ultimo bit! Basta spostare il numero del percorso una volta sola e contare il numero di bit impostati per determinare la posizione del numero nella penultima riga.

Se ci pensi; probabilmente non hai nemmeno bisogno di disturbare la generazione di una tabella di percorsi in primo luogo: potresti scrivere una funzione get_number(path, row) e usarla invece.

score 0 · Answer 2

Forse questo:

Crea una lista t di indicatori di sinistra o destra (0: a sinistra, 1: a destra) per tutti i livelli-1: Quindi nel tuo esempio t ha inizialmente 4 voci tutte a zero (segnando il primo percorso) attraverso la tua piramide (albero).

quindi ora devi contare su tutte le possibilità a sinistra o a destra ad ogni livello (eccetto il livello 0, che è il primo nodo) possiamo andare a destra o a sinistra:

Python:

pyr = [
        [1] ,     
        [5 ,8]     ,  
        [2,5, 4]   ,  
        [8, 9, 3, 1]   ,
        [2, 8,3, 7, 2] ]

pyrD = len(pyr)-1

t = [0]*pyrD

def getNodes(t):
      print("---------------")
      print("leftRightIndices: " , t)
      nodesIdx = [0]
      nodes = [ pyr[0][nodesIdx[0]] ]
      for idx,LorR in enumerate(t):
          nodesIdx.append( nodesIdx[idx]+LorR )
          nodes.append(pyr[idx+1][nodesIdx[idx+1]])

      print("nodes: " , nodes)
      print(nodes)


done = False
while not done:

    getNodes(t)

    for i in range(0,pyrD):
        carryOver = (t[i] + 1) > 1
        if not carryOver:
            t[i]+=1
            break;
        else:
            if i == pyrD-1:
                done = True
            t[i] = 0;

Che dà:

    ---------------
leftRightIndices:  [0, 0, 0, 0]
nodes:  [1, 5, 2, 8, 2]
---------------
leftRightIndices:  [1, 0, 0, 0]
nodes:  [1, 8, 5, 9, 8]
---------------
leftRightIndices:  [0, 1, 0, 0]
nodes:  [1, 5, 5, 9, 8]
---------------
leftRightIndices:  [1, 1, 0, 0]
nodes:  [1, 8, 4, 3, 3]
---------------
leftRightIndices:  [0, 0, 1, 0]
nodes:  [1, 5, 2, 9, 8]
---------------
leftRightIndices:  [1, 0, 1, 0]
nodes:  [1, 8, 5, 3, 3]
---------------
leftRightIndices:  [0, 1, 1, 0]
nodes:  [1, 5, 5, 3, 3]
---------------
leftRightIndices:  [1, 1, 1, 0]
nodes:  [1, 8, 4, 1, 7]
---------------
leftRightIndices:  [0, 0, 0, 1]
nodes:  [1, 5, 2, 8, 8]
---------------
leftRightIndices:  [1, 0, 0, 1]
nodes:  [1, 8, 5, 9, 3]
---------------
leftRightIndices:  [0, 1, 0, 1]
nodes:  [1, 5, 5, 9, 3]
---------------
leftRightIndices:  [1, 1, 0, 1]
nodes:  [1, 8, 4, 3, 7]
---------------
leftRightIndices:  [0, 0, 1, 1]
nodes:  [1, 5, 2, 9, 3]
---------------
leftRightIndices:  [1, 0, 1, 1]
nodes:  [1, 8, 5, 3, 7]
---------------
leftRightIndices:  [0, 1, 1, 1]
nodes:  [1, 5, 5, 3, 7]
---------------
leftRightIndices:  [1, 1, 1, 1]
nodes:  [1, 8, 4, 1, 2]