Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
Algoritmi - elementi in comune tra n colonne di una matrice
Forum - Algoritmi - elementi in comune tra n colonne di una matrice

Pagine: [ 1 2 ] Precedente | Prossimo
Avatar
mikemuntain (Normal User)
Newbie


Messaggi: 7
Iscritto: 28/11/2009

Segnala al moderatore
Postato alle 12:51
Sabato, 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

PM Quote
Avatar
MrC (Member)
Newbie


Messaggi: 19
Iscritto: 28/11/2009

Segnala al moderatore
Postato alle 15:37
Sabato, 28/11/2009
Hai qualche nozione di Algebra Lineare?

http://it.wikipedia.org/wiki/Algebra_lineare :pat:


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 :-|

PM Quote
Avatar
MrC (Member)
Newbie


Messaggi: 19
Iscritto: 28/11/2009

Segnala al moderatore
Postato alle 15:51
Sabato, 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. :noway:

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 :om:

Ultima modifica effettuata da MrC il 02/12/2009 alle 21:12
PM Quote
Avatar
mikemuntain (Normal User)
Newbie


Messaggi: 7
Iscritto: 28/11/2009

Segnala al moderatore
Postato alle 0:16
Lunedì, 30/11/2009
Testo quotato

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. :noway:

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 :om:



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

PM Quote
Avatar
MrC (Member)
Newbie


Messaggi: 19
Iscritto: 28/11/2009

Segnala al moderatore
Postato alle 14:03
Lunedì, 30/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
PM Quote
Avatar
MrC (Member)
Newbie


Messaggi: 19
Iscritto: 28/11/2009

Segnala al moderatore
Postato alle 14:15
Lunedì, 30/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

:k:

Ultima modifica effettuata da MrC il 30/11/2009 alle 14:17
PM Quote
Avatar
mikemuntain (Normal User)
Newbie


Messaggi: 7
Iscritto: 28/11/2009

Segnala al moderatore
Postato alle 0:52
Martedì, 01/12/2009
ok perfetto sei proprio un genio:k:
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 :hail: gentilissimo come sempre muntain:asd:

Ultima modifica effettuata da mikemuntain il 01/12/2009 alle 4:02
PM Quote
Avatar
MrC (Member)
Newbie


Messaggi: 19
Iscritto: 28/11/2009

Segnala al moderatore
Postato alle 15:04
Mercoledì, 02/12/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.

PM Quote
Avatar
mikemuntain (Normal User)
Newbie


Messaggi: 7
Iscritto: 28/11/2009

Segnala al moderatore
Postato alle 15:51
Mercoledì, 02/12/2009
Testo quotato

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

PM Quote
Pagine: [ 1 2 ] Precedente | Prossimo