mikemuntain (Normal User)
Newbie
Messaggi: 7
Iscritto: 28/11/2009
|
salve inanzitutto vorrei farei i complimenti a tutti i moderatori di questo forum davvero bellissimo e completo.
Vorrei porvi un problemi io ho una matrice di booleani dove al suo interno ci sono vari true e false, adesso io vorrei prendere le righe o le colonne a gruppi n dove n viene dato da input e vedere quali elementi hanno in comune.
Esempio:
ho questa matrice e una 6x6
codice:
a b c d e g
a F T T T F T
b T F F T F F
c T F F T T T
d T T T F T F
e F F T T F T
g T F T F T F
dove le lettere sono degli indici puremente indicativi adesso io dovrei per esempio prendere dei gruppi di n righe o colonne, ad esempio n=3 e dovrei prendere tutte le possibili combinazioni di tre righe o colonne e vedere quali sono gli elementi in comune tra tutti e tre ad esempio:
il gruppo a-c-e ha in comune a in comune tra tutte e tre d e g, e cosi via....
Adesso io ho provato con un brute-force nel senso a crearmi tutte le possibili combinazioni di n righe o colonne ma lo cosa e abbastanza lenta.
Spero abbiate capito cosa voglio realizzare spero nella vostra bonta nell'aiutarmi perchè ne sto uscendo veramente pazzo, mi bastano alcuni suggerimenti vi prego aiutatemiiiiii
Ringrazio a tutti ancipatamente a presto
|
|
MrC (Member)
Newbie
Messaggi: 19
Iscritto: 28/11/2009
|
Hai qualche nozione di Algebra Lineare?
http://it.wikipedia.org/wiki/Algebra_lineare
Al momento non ho voglia di pensare e cercare una soluzione algoritimica al tuo problema, in quanto è tuo , ma ti posso consigliare di ricercarlo in quella "zona".
Come informatico ti posso consigliare una struttura dati migliore per velocizzare il processo:
un boolean è T o F cioè 0 o 1, se usi una matrice di INTeri ne fai stare (32) in una sola cella e per confrontarli tra loro ti basta un operazione ! XOR
Se poi ti serve un valore preciso basta una masKera di bit cioè int[ pos ] & ( 1 << indirizzo_bool_voluto )
La cosa è più complicata, ma se punti alla velocità molto probabilmente è meglio
|
|
MrC (Member)
Newbie
Messaggi: 19
Iscritto: 28/11/2009
|
PS.
non avendo nessuna ipotesi di correlazione tra gli elementi, le righe o le colonne della tua matrice,
ed essendo le sottomatrici SxN in numero S su N
puoi ottenere da 1 a S!/N!(s-N)! sottomatrici SxN distinte.
Rovesciando il problema sulla "scelta per colonne" dovrai calcolare la trasposta della matirce e ripetere l'algoritmo.
Certo se hai altre ipotesi, tipo come si ottiene la matrice, si può valutare meglio il problema.
Tieni presente che stati lavorando su questo spazio:
http://it.wikipedia.org/wiki/Matrice_quadrata
e per quanto riguarda il linuaggio binario: se A<>B e B<>C A=C
Ultima modifica effettuata da MrC il 02/12/2009 alle 21:12 |
|
mikemuntain (Normal User)
Newbie
Messaggi: 7
Iscritto: 28/11/2009
|
Postato originariamente da MrC:
PS.
non avendo nessuna ipotesi di correlazione tra gli elementi, le righe o le colonne della tua matrice,
ed essendo le sottomatrici SxN in numero S!, dove S è il numero di righe/colonne scelte ( http://it.wikipedia.org/wiki/Permutazione )
puoi ottenere da 1 a S! sottomatrici SxN distinte.
Rovesciando il problema sulla "scelta per colonne" dovrai calcolare la trasposta della matirce e ripetere l'algoritmo.
Certo se hai altre ipotesi, tipo come si ottiene la matrice, si può valutare meglio il problema.
Tieni presente che stati lavorando su questo spazio:
http://it.wikipedia.org/wiki/Matrice_quadrata
e per quanto riguarda il linuaggio binario: se A<>B e B<>C A=C
|
grazie del consiglio ma non ho capito bene cosa vuoi dire quando parli di matrice ed una maskera di bit comunque dove c'è true nella matrice significa che per esempio a e "amico" di b e viceversa quindi io dovrei vedere a gruppi di n quanti amici hanno in comune
|
|
MrC (Member)
Newbie
Messaggi: 19
Iscritto: 28/11/2009
|
se al posto di
bool matrice[n][n]
metti
unsigned long matrice[n][n/log2(ULONG_MAX)]
avrai che ogni cella è composta da log2(ULONG_MAX) bit (Es. 32)
es. nXn = 64x64
0 1 ... 63
0 T T ... F
1 F T ... T
.
.
63 T F ... F
diventa semplicemente un 64x2 con valori interi
0 1
0 12343 4635233
1 38736 2393
.
.
63 23443 3434
Ultima modifica effettuata da MrC il 30/11/2009 alle 14:16 |
|
MrC (Member)
Newbie
Messaggi: 19
Iscritto: 28/11/2009
|
Esempio esplicativo:
tu hai la matrice così fatta (uso 1 al posto di True e 0 al posto di False)
0010
0101
1110
0111
usando degli interi diventa semplicemente
2
5
14
7
per vedere gli elementi comuni (es. tra le ultime 2) ti basta fare quindi un NOT XOR
NOT (14 XOR 7) = NOT( 9 ) = NOT( 1001 ) = 6 = 0110
Ultima modifica effettuata da MrC il 30/11/2009 alle 14:17 |
|
mikemuntain (Normal User)
Newbie
Messaggi: 7
Iscritto: 28/11/2009
|
ok perfetto sei proprio un genio
Adesso c'è da risolvere un piccolo problemino perchè ha me servirebbe confrontare tutte le possibili combinazioni di n righe con n dato in input dall'utente.
per esempio io in input ho una matrice cosi fatta
0 1 1 1 0 1
1 0 0 1 0 0
1 0 0 1 1 1
1 1 1 0 1 0
0 0 1 1 0 1
1 0 1 0 1 0
e dovrei dare in output la il gruppo di n righe che hanno più colonne di 1 in comune
per esempio avendo un n=3 ed una matr 6x6 dovrei provare tutte le combinazioni del tipo
123
124
125
...
...
e se noti il gruppo di righe 0-2-4 hanno in comune le colonne 3 e 5 dove ci stanno gli uno
confido nel tuo aiuto gentilissimo come sempre muntain
Ultima modifica effettuata da mikemuntain il 01/12/2009 alle 4:02 |
|
MrC (Member)
Newbie
Messaggi: 19
Iscritto: 28/11/2009
|
>dovrei dare in output la il gruppo di n righe che hanno più colonne di 1 in comune
>per esempio avendo un n=3 ed una matr 6x6 dovrei provare tutte le combinazioni del tipo
123
124
125
...
...
> e se noti il gruppo di righe 0-2-4 hanno in comune le colonne 3 e 5 dove ci stanno gli uno
Le sottomatrici che vai a considerare sono quadrate?
Tipo la tua matice NxN con N=4 è:
0101
0000
1111
1010
Se l'utente inserisce 2
ti servono le sottomatici
0101
0000
0101
1111
0101
1010
0000
1111
0000
1010
1111
0101
?
oppure tutte le sottomatrici 2x2
01
00
10
00
...
?
Ti serve vedere gli elementi comuni in tutte le righe o solo le righe che hanno tutti gli elementi uguali a 1 nelle stesse posizioni?
0123
----
0101
0011
per me queste 2 righe hanno gli elementi 0 e 3 uguali.
Se ti serve sapere tutti gli elementi uguali a 1 in tutte le righe ti basta un bel AND
01010010 AND
01010101 AND
11110000 AND
------------
01010000
(Tutti gli elementi comuni in tutte le righe nella stessa posizione uguali a 1)
NOT 01010010 = 10101101 AND
NOT 01010101 = 10101010 AND
NOT 11110000 = 00001111 AND
---------------------------
00001000
(Tutti gli elementi comuni in tutte le righe nella stessa posizione uguali a 0)
01010000 OR
00001000 =
------------
01011000
(Tutti gli elementi comuni in tutte le righe nella stessa posizione)
Stai attento che fare
01010010 XOR
01010101 XOR
11110000 XOR
------------
11110111
non è la stessa cosa
----------------------------
Posso chiederti cosa devi risolvere?
Se si tratta di trovare il rango di una matrice o cose simili vi sono tecniche molto più sofisticate che si basano su principi matematici.
|
|
mikemuntain (Normal User)
Newbie
Messaggi: 7
Iscritto: 28/11/2009
|
Postato originariamente da MrC:
>dovrei dare in output la il gruppo di n righe che hanno più colonne di 1 in comune
>per esempio avendo un n=3 ed una matr 6x6 dovrei provare tutte le combinazioni del tipo
123
124
125
...
...
> e se noti il gruppo di righe 0-2-4 hanno in comune le colonne 3 e 5 dove ci stanno gli uno
Le sottomatrici che vai a considerare sono quadrate?
Tipo la tua matice NxN con N=4 è:
0101
0000
1111
1010
Se l'utente inserisce 2
ti servono le sottomatici
0101
0000
0101
1111
0101
1010
0000
1111
0000
1010
1111
0101
?
oppure tutte le sottomatrici 2x2
01
00
10
00
...
?
Ti serve vedere gli elementi comuni in tutte le righe o solo le righe che hanno tutti gli elementi uguali a 1 nelle stesse posizioni?
0123
----
0101
0011
per me queste 2 righe hanno gli elementi 0 e 3 uguali.
Se ti serve sapere tutti gli elementi uguali a 1 in tutte le righe ti basta un bel AND
01010010 AND
01010101 AND
11110000 AND
------------
01010000
(Tutti gli elementi comuni in tutte le righe nella stessa posizione uguali a 1)
NOT 01010010 = 10101101 AND
NOT 01010101 = 10101010 AND
NOT 11110000 = 00001111 AND
---------------------------
00001000
(Tutti gli elementi comuni in tutte le righe nella stessa posizione uguali a 0)
01010000 OR
00001000 =
------------
01011000
(Tutti gli elementi comuni in tutte le righe nella stessa posizione)
Stai attento che fare
01010010 XOR
01010101 XOR
11110000 XOR
------------
11110111
non è la stessa cosa
----------------------------
Posso chiederti cosa devi risolvere?
Se si tratta di trovare il rango di una matrice o cose simili vi sono tecniche molto più sofisticate che si basano su principi matematici. |
grazie ancora dei tuoi consigli come sempre molto utili..
allora la mia matrice e quadrata e mi serve prendere tutte le sotto matrici così
0101
0000
1111
1010
Se l'utente inserisce 2
0101
0000
0101
1111
0101
1010
0000
1111
0000
1010
1111
0101
poi mi serve vedere solo le righe che hanno tutti gli elementi uguali a 1 nelle stesse posizioni.
comunque quello che dovrei realizzare e avendo in input due liste di persone vedere a gruppi gi k persone ki a più persone in comune
grazie come sempre del tuo aiuto |
|