Algoritmi - elementi in comune tra n colonne di una matrice

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

Hai qualche nozione di Algebra Lineare?

it.wikipedia.org/wiki/…


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

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:
it.wikipedia.org/wiki/…

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

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

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

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

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