Enumerare tutte le k-partizioni dell'array 1d con N elementi?

Question

Questa sembra una semplice richiesta, ma Google non è mio amico perché "partizione" segna un sacco di successi nello spazio del database e del filesystem.

Ho bisogno di enumerare tutte le partizioni di un array di valori N (N è costante) in k sotto-array. I sotto-array sono solo questo: un indice iniziale e un indice finale. L'ordine generale dell'array originale verrà mantenuto.

Ad esempio, con N = 4 e k = 2:

[ | a b c d ] (0, 4) 
[ a | b c d ] (1, 3) 
[ a b | c d ] (2, 2) 
[ a b c | d ] (3, 1) 
[ a b c d | ] (4, 0) 

E con k = 3:

[ | | a b c d ] (0, 0, 4) 
[ | a | b c d ] (0, 1, 3) 
    : 
[ a | b | c d ] (1, 1, 2) 
[ a | b c | d ] (1, 2, 1) 
    : 
[ a b c d | | ] (4, 0, 0) 

Sono abbastanza sicuro che questo non è un problema originale (e no, non è compito a casa), ma mi piacerebbe farlo per ogni k < = N, e sarebbe bello se i passaggi successivi (come k cresce) hanno approfittato dei risultati precedenti.

Se si dispone di un collegamento, si prega di condividere.

Answer 1

Per riutilizzare i risultati precedenti (per i valori inferiori di k), è possibile eseguire la ricorsione.

Pensa a tale partizionamento come a un elenco di indici finali (l'indice iniziale per qualsiasi partizione è solo l'indice finale dell'ultima partizione o 0 per il primo).

Quindi, il set di paratia sono solo un insieme di tutte le matrici di k interi non decrescenti tra 0 e N.

Se k delimitata, si può fare questo tramite k cicli annidati

for (i[0]=0; i[0] < N; i[0]++) { 
    for (i[1]=i[0]; i[1] < N; i[1]++) { 
    ... 
      for (i[10]=i[9]; i[10] < N; i[10]++) { 
       push i[0]==>i[10] onto the list of partitionings. 
      } 
    ... 
    } 
} 

Se k non è limitato, è possibile farlo in modo ricorsivo.

Un insieme di k partizioni tra indici S ed E si ottiene:

• Loop "fine della prima partizione" EFP tra S ed E. Per ogni valore:

  • Trova in modo ricorsivo un elenco di partizioni k-1 tra EFP e S

  • Per ogni vettore in tale elenco, "EFP" pre-pendente a quel vettore.

  • il vettore risultante di lunghezza k viene aggiunto all'elenco dei risultati.

Si prega di notare che la mia risposta produce liste di end-point di ogni fetta. Se tu (come mostra il tuo esempio) vuoi un elenco di LUNGHEZZE di ogni sezione, devi ottenere delle lunghezze sottraendo l'ultima porzione di sezione dalla fine della sezione corrente.

Answer 2

Ogni partizione può essere descritta dagli indici k-1 che separano le parti. Poiché l'ordine è preservato, questi indici devono essere non-decrescenti. Cioè, c'è una corrispondenza diretta tra sottoinsiemi di dimensioni k-1 e le partizioni che cerchi.

Per iterazione su tutti i sottoinsiemi di dimensione k-1, è possibile controllare la domanda:

How to iteratively generate k elements subsets from a set of size n in java?

L'unica antirughe è che se parti vuote sono consentiti, diversi cut-punti possono coincidere, ma un sottoinsieme può contenere ogni indice al massimo una volta. Dovrete modificare leggermente l'algoritmo sostituendo:

 processLargerSubsets(set, subset, subsetSize + 1, j + 1); 

da

 processLargerSubsets(set, subset, subsetSize + 1, j);