Piccolo gioco di combinatoria

[celeste4]

Ciao a tutti! Mi sto dilettando da un paio di giorni nel cercare un modo metodico per elencare (e ovviamente, capire quante sono!) tutte le possibili posizioni reciproche che possono assumere tre intervalli distinti (cioè, che a due a due non abbiano entrambi gli estremi uguali...per il resto possono intersecarsi, essere disgiunti o annidati come gli pare).

Finora ho separato le tre possibilità:

- che gli estremi assumano tre valori diversi (ovvero, usando numeri per non perderci negli indici - essendo interessata solo alla posizione reciproca il resto è indifferente - qui c'è solo ($[1,2], [2,3], [1,3]$);
- che gli estremi assumano quattro valori distinti;
- che gli estremi assumano cinque valori distinti;
- che gli estremi assumano sei valori distinti.

Ora, l'unico "metodo" che mi viene in mente è cominciare a disegnare la retta reale e fissare i primi due intervalli e cercare tutte le posizioni del terzo, spostare il secondo e rimuovere di nuovo il terzo in tutte le posizioni.
Tuttavia, così non escludo alcune ripetizioni (mi interessano terne non ordinate), e neanche sono certa di non dimenticarne qualcuna per strada...qualche appassionato di combinatoria ha un'idea?

[celeste4]

Uhm...era una domanda stupida?

[hamming_burst]

"celeste":Ciao a tutti! Mi sto dilettando da un paio di giorni nel cercare un modo metodico per elencare (e ovviamente, capire quante sono!) tutte le possibili posizioni reciproche che possono assumere tre intervalli distinti (cioè, che a due a due non abbiano entrambi gli estremi uguali...per il resto possono intersecarsi, essere disgiunti o annidati come gli pare).

in pratica mi pare siano banalmente le combinazioni semplici di 3 elementi presi a due a due.

Se hai l'insieme ${a,b,c}$ avrai combinazioni non ordinate di due elementi, senza ripetizioni:
${a,b}$
${a,c}$
${b,c}$

Il numero totale si calcola con il coff. binomiale: $((3),(2)) = 3$

"celeste":Ora, l'unico "metodo" che mi viene in mente è cominciare a disegnare la retta reale e fissare i primi due intervalli e cercare tutte le posizioni del terzo, spostare il secondo e rimuovere di nuovo il terzo in tutte le posizioni.
Tuttavia, così non escludo alcune ripetizioni (mi interessano terne non ordinate), e neanche sono certa di non dimenticarne qualcuna per strada...qualche appassionato di combinatoria ha un'idea?

Ti serve un metodo algoritmico?

[celeste4]

In effetti non si tratta proprio di questo, devo elencare terne non ordinate di coppie che coinvolgono un certo numero di elementi, dunque, ad esempio con 4 elementi:
$(1,4), (1,3), (3,4)$
$(1,4), (1,3), (1,2)$
$(1,4), (2, 4), (3,4)$
$(1,4), (2,4), (2,3)$
eccetera...

[hamming_burst]

"celeste":In effetti non si tratta proprio di questo, devo elencare terne non ordinate di coppie che coinvolgono un certo numero di elementi, dunque, ad esempio con 4 elementi:
$(1,4), (1,3), (3,4)$
$(1,4), (1,3), (1,2)$
$(1,4), (2, 4), (3,4)$
$(1,4), (2,4), (2,3)$
eccetera...

uh è un pochetto più incriccata messa così.
Sembra una doppia combinazione, sempre semplice e senza ripetizioni (all'incirca)

prima ti crei l'insieme delle combinazioni di 4 elementi presi a due a due
${1,2,3,4}$
$a = {1,2}$
$b = {1,3}$
$c = {1,4}$
$d = {2,3}$
$e = {2,4}$
$f = {3,4}$

poi ti crei l'insieme delle combinazioni di $((4),(2))$ elementi presi a tre a tre, sostituendo.
${a,b,c,d,e,f}$
${a,b,c} -> {{1,2},{1,3},{1,4}}$
${a,b,d} -> {{1,2},{1,3},{2,3}}$
ecc..
${a,b,e} {a,b,f} {a,c,d} {a,c,e} {a,c,f} {a,d,e} {a,d,f} {a,e,f} {b,c,d}$
$ {b,c,e} {b,c,f} {b,d,e} {b,d,f} {b,e,f} {c,d,e} {c,d,f} {c,e,f} {d,e,f}$

In totale ci sono $((((4),(2))),(3)) = 20$ combinazioni. In generale avrai $((((n),(2))),(3))$ combinazioni.

ok? è giusto il problema?

Per l'elencazione non mi hai risposto, ti serve un algoritmo, un metodo computazionale? che devi farci?
Ti posso anche proporre un algoritmo in uno pseudo linguaggio.

[celeste4]

Uh cavoli, hai ragione, non era poi così complicato. Grazie!
Per l'elencazione...io finora procedo disegnando intervalli e sperando di non dimenticare casi. Avevo pensato di trovare un algoritmo e poi programmarmelo ma non sapevo come. Ma forse ora che la vicenda è più chiara potrei farcela

[hamming_burst]

"celeste":Uh cavoli, hai ragione, non era poi così complicato. Grazie!
Per l'elencazione...io finora procedo disegnando intervalli e sperando di non dimenticare casi. Avevo pensato di trovare un algoritmo e poi programmarmelo ma non sapevo come. Ma forse ora che la vicenda è più chiara potrei farcela

se è per piccoli valori ed è un gioco, puoi provare ad usare manualmente i solver online: esempio.

se è per cose più "importanti" ed i valori di $n$ sono grandi stai attenta a scrivere l'algoritmo, il tempo di calcolo diventa esponenziale se non scritto in modo accurato; avendo partizioni di 2 e 3 elementi sei in un caso molto particolare e ci sono modi per rendere l'algoritmo molto efficiente. Prova a scriverlo se hai difficoltà basta scrivere, è un prob. abb. classico quello dell'enumerazione e penso esistano anche funzioni di qualche libreria se usi un linguaggio in particolare, ma avendo doppie combinazioni forse fai prima a scriverlo da zero, sono poche righe se ricordo bene.

[celeste4]

Ok, grazie, proverò!