Come eseguire iterazioni con combinazioni di array con somma costante in modo efficiente?

Question

Ho una matrice e la sua lunghezza è X. Ogni elemento dell'array ha intervallo 1 .. L. Voglio scorrere in modo efficiente attraverso tutte le combinazioni di array che ha somma L.

soluzioni corrette per: L = 4 e X = 2

1 3 
3 1 
2 2 

soluzioni corrette per: L = 5 e X = 3

1 1 3 
1 3 1 
3 1 1 
1 2 2 
2 1 2 
2 2 1 

L'implementazione naive è (stupirsi) troppo lento per il mio problema (X ha fino a 8 nel mio caso e L è fino a 128).

Qualcuno potrebbe dirmi come si chiama questo problema o dove trovare un algoritmo veloce per il problema?

Grazie!

Answer 1

Se ho capito bene, si è dato due numeri 1 ≤ X ≤ L e si desidera generare tutte le sequenze di numeri interi positivi di lunghezza X tale somma a L.

(Nota: questo è simile al integer partition problem, ma non lo stesso, perché si considera 1,2,2 di essere una sequenza diversa da 2,1,2, mentre nel problema di partizione intero ignoriamo l'ordine, in modo che questi sono considerati per essere la stessa partizione)

le sequenze che si sta cercando corrispondono alle combinations di X -. 1 articoli di L - 1. per, se mettiamo i numeri 1 a L - 1 nell'ordine, e scegliere X - 1 di loro, quindi le lunghezze di intervalli tra il scelto i numeri sono numeri interi positivi che sommano a L.

Per esempio, supponiamo che L è 16 e X è 5. Poi scegliere 4 numeri da 1 a 15 inclusi:

Aggiungi 0 all'inizio e 16 alla fine , e gli intervalli sono:

e 3 + 4 + 1 + 6 + 2 = 16 come richiesto.

Così generate the combinations di X - 1 articoli di L-1, e per ciascuno di essi, convertirlo in una partizione trovando gli intervalli. Per esempio, in Python si potrebbe scrivere:

from itertools import combinations 

def partitions(n, t): 
    """ 
    Generate the sequences of `n` positive integers that sum to `t`. 
    """ 
    assert(1 <= n <= t) 
    def intervals(c): 
     last = 0 
     for i in c: 
      yield i - last 
      last = i 
     yield t - last 
    for c in combinations(range(1, t), n - 1): 
     yield tuple(intervals(c)) 

>>> list(partitions(2, 4)) 
[(1, 3), (2, 2), (3, 1)] 
>>> list(partitions(3, 5)) 
[(1, 1, 3), (1, 2, 2), (1, 3, 1), (2, 1, 2), (2, 2, 1), (3, 1, 1)] 

Ci sono (L-1)!/(X - 1)! (L - X)!combinazioni di X - 1 articoli su L - 1, per cui l'esecuzione di questo algoritmo (e le dimensioni della sua uscita) è esponenziale L. Tuttavia, se non si conta l'output, è necessario solo lo spazio O (L).

Con L = 128 e X = 8, ci sono 89,356,415,775 partizioni, quindi ci vorrà un po 'per l'uscita tutti!

(Forse se si spiega il motivo per cui si sta Computing queste partizioni, potremmo essere in grado di suggerire un modo di soddisfare le vostre esigenze senza dover a tutti loro produrre effettivamente.)