Partizioni di un numero

[Nemo02]

Ciao a tutti sto cercando di trovare un idea per creare la lista infinita di liste infinite come nell'immagine dove l'insieme dei numeri in azzurro danno le partizioni di 5 se ci aggiungo quelle blu sono le partizioni si 6 quelle verdi di 7 e così via. Grazie in anticipo.

Spoiler

 

[Mursey]

sto cercando di trovare un idea per creare la lista

Visto che abbiamo la regola:
La sezione Programmazione e le sue sottosezioni non offrono un servizio di risoluzione compiti scolastici.
E' possibile chiedere aiuto ma allegando il codice scritto o le prove fatte.

Tu cosa hai fatto e su cosa ti blocchi?
Devi scriverlo in che linguaggio?

 

[Nemo02]

Grazie avevo letto il regolamento e non è un compito scolastico comunque avevo pensato a un programma così ma è sbagliato poich+ genera troppe stream

ones = 1: ones

partizioni = ones : map (f) partitizioni

f (x:xs) = ((x+1):xs) ++ (f xs)

 

[M1n021]

Ciao a tutti sto cercando di trovare un idea per creare la lista infinita di liste infinite come nell'immagine dove l'insieme dei numeri in azzurro danno le partizioni di 5 se ci aggiungo quelle blu sono le partizioni si 6 quelle verdi di 7 e così via. Grazie in anticipo.

Ciao, più o meno credo di aver capito quello che intendi fare, ma non penso che parlare di "infinito" abbia molto senso nell'ambito della programmazione.
Ammettiamo poi che tu riesca a ottenere un risultato come quello da te postato (finito ovviamente, per esempio fino a n=100), dove ogni riga corrisponde ad un vettore di numeri; non avendo i colori come fai ad isolare per esempio le partizioni di 27 dalla matrice!?
Forse se spieghi cosa devi fare con queste partizioni possiamo esserti maggiormente di aiuto.

 

[Nemo02]

Ciao, più o meno credo di aver capito quello che intendi fare, ma non penso che parlare di "infinito" abbia molto senso nell'ambito della programmazione.
Ammettiamo poi che tu riesca a ottenere un risultato come quello da te postato (finito ovviamente, per esempio fino a n=100), dove ogni riga corrisponde ad un vettore di numeri; non avendo i colori come fai ad isolare per esempio le partizioni di 27 dalla matrice!?
Forse se spieghi cosa devi fare con queste partizioni possiamo esserti maggiormente di aiuto.

Una volta che ho questo stream di stream per prendere le partizioni di 27 faccio un takewhile testa della lista == 27 e poi di queste liste prendo di nuovo takewhile sommasegmenti iniziali == 27 e questa parte l'ho già scritta l'unica cosa è scrivere la funzione che mi genera lo stream di stream di tutte le partizioni

 

[M1n021]

Non conosco il "gergo" a cui fai riferimento, ma penso che la stai facendo più semplice del dovuto...

In ogni caso, visto che come già detto non ha molto senso parlare di liste infinite, quale deve essere il massimo numero di cui calcolare le partizioni?

 

[Nemo02]

Non è gergo ma linguaggio di programmazione funzionale haskell il quale permette di lavorare con stream di stream ovvero liste infinite e il problema si concentra tutto su quello creare lo stream di stream di tutte le partizioni e poi attraverso le funzioni sopra citate estrapolare le partizioni richieste. Senza questo stream di stream il programma che genera tute le partizioni di un numeor dato in haskel è di due righe e ha poco senso parlare di questo. Se eerve scrivo il codice che ho scritto a parole sopra

 

[M1n021]

Ipotizziamo di avere la lista di liste per i numeri che vanno da 1 a 8, da quello che ho capito per determinare il numero di partizioni per esempio del numero 6 si parte dalla riga iniziale e si va avanti fino alla riga che inizia con lo stesso 6, mentre per estrapolare la partizione dalla generica riga si considera la sequenza di elementi iniziali finché la loro somma non raggiunge il valore di 6. Giusto?

Se quanto appena detto è corretto, allora è fondamentale l'ordine in cui si susseguono le varie righe.
Consideriamo il seguente esempio:



Nei primi 8 schemi abbiamo le partizioni in ordine lessicografico dei numeri che vanno da 1 a 8, mentre lo schema finale (che dovrebbe essere quello che ti serve) contiene le stesse sequenze presenti nella tabella delle partizioni del numero 8, ma in un ordine diverso, tale da rispettare i criteri di estrapolazione sopra descritti.
Per ottenere la tabella finale ho ordinato le partizioni del numero 8 in modo che compaiono prima le sequenze che contengono le partizioni del numero 1, poi le sequenze che contengono le partizioni del numero 2, poi le sequenze che contengono le partizioni del numero 3, .... e così via fino al numero 8.
E' l'unico modo per ottenere questo risultato? Si può fare di meglio? Non lo so, ci devo pensare, ma almeno iniziamo a formalizzare il problema in maniera più chiara.
Fammi sapere se quello che ho scritto è corretto.

 

[Nemo02]

part xs =  map ( ++ [1]) xs ++ map myLast xs

myLast [x] = [x+1]
myLast (x:xs) = [x] ++ myLast xs

Se diamo in pasto a part la lista di liste di partizioni di n mi scrive la lista di liste di partizioni di n+1 quindi dovrei riuscire ad applicare ricorsivamente part partendo da [[1]] ma mi non reisce a girare ma in stackoverflow

 

[M1n021]

@Nemo02 ovviamente non sei costretto a stare dietro alla mia ignoranza relativamente all'haskell, ma penso che se uno vuole farsi capire da una platea più ampia, uno sforzo potrebbe pure farlo. Anche perché si può discutere di un problema o di un algoritmo anche in termini generali e poi una volta trovata la quadra tradurlo in un determinato linguaggio di programmazione. Ed è quello che ho cercato di fare nel mio precedente messaggio, ma l'hai ignorato.
In ogni caso se la tabella "sequenze ordinate" sopra postata per n_max=8 è corretta, allora credo di aver trovato un modo relativamente semplice per ottenerla, basato sullo generare le sole partizioni di n_max, per poi ordinarle secondo un semplice criterio di ordinamento.

 

[Nemo02]

Mi veniva semplice scriverlo così perchè in haskell si usano bene le liste infinite comunque non siamo costretti ad usarlo l'idea è aggiungere 1 alla fine di ogni lista e sommare 1 sull'ultimo elemento di tutte le liste così creo le partizioni da n a n+1. Dell'immagine non è giusto l'ordine dell'8

 

[M1n021]

Dell'immagine non è giusto l'ordine dell'8

Precisamente a quale schema ti riferisci e quale sarebbe il problema?

 

[Nemo02]

È giusto l'ordine di sequenze ordinate avevo letto male comunque dovrei aver risolto con questa idea di seguito allego anche il codice haskell per chi fosse interessato. si può tranquillamente portare in qualsiasi linguaggio che riesca ad usare le liste infinite.

L'idea è se ho le partizioni di n posso generare quelle di n+1 semplicemente aggiungendo uno sull'ultimo elemento di ogni partizione e poi attaccando uno a tutte le partizioni (vanno tolte a queste tutte le liste non ordinate se no si creano doppioni).
Adesso però usare come ricorsione questa funzione non va bene perchè non produce mai nulla quindi non posso andarla ad interrogare una volta che l'ho lanciata.
Da qui l'utilizzo delle liste infinite così da generare sempre qualcosa. Parto dalla lista infinita di tutti 1 e la lista infinita che inizia per due e poi continua con tutti 1 a questo punto o due liste infinite all'n-esima iterazione cosa faccio prendo la testa delle liste affinché la somma faccia proprio n e quindi faccio girare una volta il programma di prima che mi torna tutte le partizioni di n+1 a questo punto attacco ad ogni lista una lista infinita di 1 e poi concatena quasta lista di liste a quella che gia avevo (con una funzione che mi toglie le liste duplciate perchè ci sono) e così ho una funzione ricorsiva che generara una lista infinita di liste infinite.
(il codice funziona ma va migliorato)

part1 (x:xs) = map (++ones) (filter (isOrder)(map myLast xs))

myLast [x] = [x+1]
myLast (x:xs) = [x] ++ myLast xs

ones :: [Int]
ones = [1,1..]

ex = [ones] ++ [([2]++ones)]

union n (ys:yss) (xs:xss)
 | yss == [] && (take (n+2) ys) == (take (n+2) xs) = (xss)
 | yss == [] = (xs:xss)
 | (take (n+2) ys) == (take (n+2) xs) = union n yss xss
 | otherwise = [xs]

myTakeWhile n (x:xs)
 | x == n = [x]
 | otherwise = [x] ++ myTakeWhile (n-x) xs

isOrder [] = True
isOrder [x] = True
isOrder (x:y:xs)
 | x >= y = isOrder (y:xs)
 | otherwise = False

allPartition = allP 2 ex

allP n xs =
 let ys = xs ++ part1 (map (myTakeWhile n) xs) in ys ++ (union n ys (allP (n+1) ys))

partsFromAll n = map (myTakeWhile n) (myTakeW n allPartition)

myTakeW n (xs:xss)
 | n == head xs = [xs]
 | otherwise = [xs] ++ myTakeW n xss

sicuramente si può migliorare però come brutal force funziona

 

[M1n021]

Scusa, ma continuo a non capire cosa stai cercando di ottenere precisamente (e a tal proposito sarebbe utile sapere cosa devi farci con queste partizioni).

Dal post iniziale mi sembrava di capire che il tuo scopo fosse quello di generare una sequenza come quella da te postata con i numeri colorati che ti permettesse di estrarre le partizioni di n mediante la seguente procedura da te descritta:

Una volta che ho questo stream di stream per prendere le partizioni di 27 faccio un takewhile testa della lista == 27 e poi di queste liste prendo di nuovo takewhile sommasegmenti iniziali == 27

Ora invece mi pare che tu ti stia soffermando su come ottenere le partizioni di n+1 partendo da quelle di n. E a tal proposito non mi sembra che per passare per esempio dalle partizioni di 7 a quelle di 8 sia sufficiente "attaccare uno a tutte le partizioni".

Visto che il problema mi sembrava interessante ho provato a risolverlo pure io, ma se non chiarisci i punti sopra esposti diventa difficile capire su cosa confrontarsi...

 

[BAT]

L'idea è se ho le partizioni di n posso generare quelle di n+1 semplicemente aggiungendo uno sull'ultimo elemento di ogni partizione e poi attaccando uno a tutte le partizioni

non mi sembra corretto perché rischi di saltarne parecchie: guarda per esempio le tabelle che ha generato @M1n021 nel suo post precedente, in particolare le partizioni di 4 e 5: partizione di 5=<3,2> non la puoi ottenere dalle partizioni di 4, così come la partizione di 6=<2,2,2> non la puoi ottenere dalle partizioni di 5
se ben ricordo, il numero di possibili partizioni di un intero n cresce in modo esponenziale al crescere di n, quindi più n sarà grande, sempre più partizioni perderai se ti limiti ad aggiungere degli "1" ad uno schema di partizioni precedente.