[C++] Sequenze calcolo combinatorio

Messaggioda Super Squirrel » 08/02/2019, 01:01

Dal momento che spesso mi avrebbe fatto comodo avere a disposizione qualcosa del genere, ho deciso di implementare una piccola libreria basata su una classe template che, a partire da un array di $n$ elementi e un intero $k$, è in grado di generare tutte le possibili sequenze relative a:
- permutazioni semplici;
- combinazioni semplici;
- combinazioni con ripetizione;
- disposizioni semplici;
- disposizioni con ripetizione.

Al momento sono alle prese con la partizione in $m$ sottoinsiemi di $k_i$ elementi ciascuno (tale che $sum_(i = 1)^(m)k_i=n$), che credo di aver quasi risolto utilizzando le combinazioni semplici in $m-1$ step. Facendo qualche ricerca in rete però ho notato che queste partizioni vengono definite "ordinate", a cosa è dovuto quest'attributo?

Ci sono poi le permutazioni con ripetizione, il cui numero credo dovrebbe essere uguale a quello delle suddette partizioni, ma su come generarle sono ancora in alto mare. Un esempio applicativo potrebbe essere quello di generare tutti gli anagrammi diversi della parola FARFALLA.

Esiste qualche altro tipo di sequenza che vale la pena implementare?
Super Squirrel
Junior Member
Junior Member
 
Messaggio: 343 di 346
Iscritto il: 16/05/2013, 22:05

Re: [C++] Sequenze calcolo combinatorio

Messaggioda apatriarca » 08/02/2019, 02:12

L'utilità suppongo dipenda molto dal tipo di programmi che sei interessato a sviluppare. Sinceramente non mi è per esempio credo mai capitato di aver bisogno di algoritmi come quelli che hai descritto. Mi è capitato di aver invece bisogno di sceglierne una casuale in modo "uniforme" per esempio.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5187 di 5196
Iscritto il: 08/12/2008, 20:37
Località: Londra


Torna a Informatica

Chi c’è in linea

Visitano il forum: Camillo, Exabot [Bot], GiovanniMontanaro e 7 ospiti