Trova tutti i possibili sottoarray di una matrice

Prendiamo un array di dimensioni n . Esistono 2 ⁿ possibili sottoarray di questo array. Prendiamo la matrice di esempio di dimensione 4: [1, 2, 3, 4] . Esistono 2 sottosistemi ⁴ .

Il sottoarray del set vuoto ( [] ) è lo 0 ^th ( 0000 ). Il sottoarray di [1] , è il secondo ( 0001 ), il sottoarray di [2] è il secondo ... ( 0010 ) e il sottoarray [1, 2] è il terzo ( 0011 ) . Dovresti vedere dove sta andando.

Per questo non è necessaria alcuna ricorsione. L'insieme dei sottoarray è la rappresentazione binaria del valore n ^th che va da 0 a 2 ⁿ - 1.

Con questa realizzazione, la generazione di tutti i sottoarray per un determinato array dovrebbe essere una questione banale di iterazione degli interi e considerarli come campi bit per se un particolare elemento si trova nel sottoarray oppure no.

Vedi anche Numero di combinazioni k per tutti k su Wikipedia.

Vorrei sottolineare che questo è probabilmente il modo giusto per farlo in C e lingue simili. Cercare di forzare la ricorsione, le liste e il backtracking su quello che altrimenti sarebbe un semplice problema iterativo con una risposta chiara e comprensibile potrebbe non essere l'approccio migliore.

Si noti che altre risposte proposte a questo diventano rapidamente esempi e soluzioni di programmazione funzionale. La programmazione funzionale è eccezionale. Tuttavia, in un linguaggio non adatto a questo tentativo di forzare questo paradigma di programmazione su di esso sarebbe simile alla scrittura di codice C in Lisp - potrebbe non essere il modo migliore per affrontare il problema.

Devo inoltre sottolineare che il problema suggerito nella domanda è:

For instance say I have a array with [1,2,3,4] and my destination value is 5. I am trying to find all possible combinations that equal to my destination value.

Questo è un noto problema noto come problema somma sottoinsieme e ha un numero di approcci per risolverlo .. generare tutti i sottoinsiemi dell'array non è richiesto (o nemmeno desiderato) per gli approcci più veloci per risolverlo.

Si desidera enumerare ricorsivamente l'insieme di sottoliste di 1 :: 2 :: 3 :: 4 :: [] che somma a 5 . (Il :: è la notazione OCaml per la costruzione della lista.) Il passo ricorsivo nell'elaborazione dell'elenco sta dividendo l'elenco nella sua testa 1 e la sua coda 2 :: 3 :: 4 :: [] - possiamo descrivere il nostro set in questi termini?

Esistono due tipi di sottoliste di 1 :: 2 :: 3 :: 4 :: [] che sommano a 5 :

• Il primo tipo è costituito da liste che iniziano con 1 e seguite da un elenco che somma a 4 = 5 - 1 .
• Il secondo tipo consiste in sottoliste di 2 :: 3 :: 4 :: [] sommando in 5 .

Meraviglioso! Se chiamiamo partition la funzione int list -> int -> int list list trovando tutte le sottoliste richieste, la descrizione sopra descrive solo come definire partition lst per le liste lst di lunghezza n data la sua definizione per gli elenchi di lunghezza n-1 .

La scrittura della funzione in OCaml è quindi staightforward:

let rec partition lst w =
  if w = 0 then
    [[]]
  else
    match lst with
      | [] -> []
      | hd :: tl -> firstkind hd tl (w - hd) @ partition tl w
and firstkind hd tl w =
  List.map (fun lst -> hd :: lst) (partition tl w)

Sto assumendo per lo scopo di questo esercizio che non vuoi alcuna ripetizione. Ad esempio, le combinazioni per [1..4] sono

[[1],[1,2],[1,2,3],[1,2,3,4],[1,2,4],[1,3],[1,3,4],
 [1,4],[2],[2,3],[2,3,4],[2,4],[3],[3,4],[4]]

In caso contrario, il processo è lo stesso per tutte le funzioni ricorsive: individua i casi di base e individua il tuo problema più grande in termini di un problema più piccolo.

Creeremo una funzione subarrays che prende una lista e restituisce una lista di liste, una per ogni combinazione, quindi:

subarrays :: [a] -> [[a]]

Il caso base è di solito molto semplice. In questo caso, i sottoarray per una lista vuota sono una lista vuota, quindi:

subarrays [] = []

Il passaggio ricorsivo per le funzioni di lista lo spezza quasi sempre nel primo elemento, chiamato "testa" (indicato qui da x ), e il resto dell'elenco, chiamato "coda" (indicato qui da xs ). Presumiamo di conoscere già la risposta corretta per la coda, e la usiamo per costruire una risposta per la testa. Qui assegniamo il simbolo combos alla risposta per la coda:

subarrays (x:xs) = let combos = subarrays xs

Finora questo è un codice relativamente standard che si trova in quasi tutte le funzioni ricorsive in una forma o nell'altra. La parte difficile ora è che l'abbiamo risolto per una lista più piccola, come aggiungeremo un altro livello?

Per un esempio, supponiamo che combos contenga tutte le soluzioni per [2,3,4] e stai creando un elenco che contiene anche soluzioni contenenti 1 . In questo caso, puoi fare una delle tre cose per costruire la lista più grande.

• Basta avere 1 di per sé. ( [x] )
• Basta avere tutte le altre combo da sole. ( combos )
• hai aggiunto tutte le altre combo con 1 . ( map (x:) combos )

Quindi restituisci una lista contenente tutte queste possibilità:

[x] : map (x:) combos ++ combos

Questo è davvero tutto quello che c'è da fare. Ecco il programma completo in Haskell con la funzione sum test:

subarrays :: [a] -> [[a]]
subarrays [] = []
subarrays (x:xs) = let combos = subarrays xs
                   in [x] : map (x:) combos ++ combos

combosSumTo :: Int -> [Int] -> [[Int]]
combosSumTo x = filter (\y -> sum y == x) . subarrays

Per quanto riguarda il modo in cui sono venuto fuori con le tre cose, devi solo esercitarti, testare e ripetere. Quando l'ho scritto per la prima volta, ho dimenticato per sbaglio la parte [x] , ma questo è apparso nei miei test. Il trucco è non cercare di ricacciare la pila nella tua testa. Supponiamo che la chiamata ricorsiva ti dia la risposta corretta per la coda della lista.