Algoritmi - elementi in comune tra n colonne di una matrice

Forum - Algoritmi - elementi in comune tra n colonne di una matrice - Pagina 2

Pagine: [ 1 2 ]

MrC (Member)
Newbie

Messaggi: 19
Iscritto: 28/11/2009

Postato alle 16:13
Mercoledì, 02/12/2009

Hai già la risposta:

tutte le permutazioni

e

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

mikemuntain (Normal User)
Newbie

Messaggi: 7
Iscritto: 28/11/2009

Postato alle 18:23
Mercoledì, 02/12/2009

Testo quotato

Postato originariamente da MrC:

Hai già la risposta:

tutte le permutazioni

e

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

ok perfetto ai ragione ma mi potresti aiutare nella costruzione di un algoritmo che fa quello che ai detto in automatico nel senso l'utente gli passa da input la matrice, ed n
e poi crea tutte le combinazioni di n righe le mette in and, e dalla risultato dell'operazione and vede quanti 1 ha.
spero in una tua risposta perchè sei l'unico che è stato in grado di darmi una mano

MrC (Member)
Newbie

Messaggi: 19
Iscritto: 28/11/2009

Postato alle 21:42
Mercoledì, 02/12/2009

Con questo ottieni tutte le combinazioni degli elementi di un vettore.
Per te gli elementi del vettore sono dei vettori (righe matrice).

void permuta( int vect[], int i, int j )
{

    //Se vuoi risparmiare una variabile fai a = a XOR b; b = a XOR b; a = a XOR b;

    int tmp=vect;

    vect=vect[j];

    vect[j]=tmp;
}

void combinazioni( int vect[], int i, int size_vect )
{
    int j;

    if ( i==size_vect )
    {
        for ( i=0;i<size_vect;i++ )
            printf( "%d",vect );
    }

    else
        for ( j=i;j<size_vect;j++ )
        {
            permuta( vect,i,j );
            combinazioni( vect,i+1,size_vect );
            permuta( vect,i,j );
        }
}

Dopo basta fare un AND (&) di ogni elemento di ogni riga e assegnarlo ad una variabile.

Infine per contare gli 1 di questa variabile basta fare

tot_1_bit = 0;
for( i=0; i<log2(NUMERO); i++)
tot_1_bit += ( NUMERO >> i ) & 1 ;

Se poi vuoi ottenere il massimo

static int max = 0;
if( tot_1_bit > max )
max = tot_1_bit;

mikemuntain (Normal User)
Newbie

Messaggi: 7
Iscritto: 28/11/2009

Postato alle 12:30
Giovedì, 03/12/2009

Testo quotato

Postato originariamente da MrC:

Con questo ottieni tutte le combinazioni degli elementi di un vettore.
Per te gli elementi del vettore sono dei vettori (righe matrice).

void permuta( int vect[], int i, int j )
{

    //Se vuoi risparmiare una variabile fai a = a XOR b; b = a XOR b; a = a XOR b;

    int tmp=vect;

    vect=vect[j];

    vect[j]=tmp;
}

void combinazioni( int vect[], int i, int size_vect )
{
    int j;

    if ( i==size_vect )
    {
        for ( i=0;i<size_vect;i++ )
            printf( "%d",vect );
    }

    else
        for ( j=i;j<size_vect;j++ )
        {
            permuta( vect,i,j );
            combinazioni( vect,i+1,size_vect );
            permuta( vect,i,j );
        }
}

Dopo basta fare un AND (&) di ogni elemento di ogni riga e assegnarlo ad una variabile.

Infine per contare gli 1 di questa variabile basta fare

tot_1_bit = 0;
for( i=0; i<log2(NUMERO); i++)
tot_1_bit += ( NUMERO >> i ) & 1 ;

Se poi vuoi ottenere il massimo

static int max = 0;
if( tot_1_bit > max )
max = tot_1_bit;

ma l'algoritmo che mi hai dato non le combinazioni dei vettori di una matrice, e poi per il vettore fa anche le combinazioni con duplicati ed io non voglio duplicati, e poi cosa intendi per //Se vuoi risparmiare una variabile fai a = a XOR b; b = a XOR b; a = a XOR b; su che cosa lo devo fare :k:

MrC (Member)
Newbie

Messaggi: 19
Iscritto: 28/11/2009

Postato alle 19:39
Giovedì, 03/12/2009

Infatti questo è un esempio... non posso farti il programma :rofl:

scambiare 2 varibili senza una variabile d'appoggio:

a = 1 // 0..0001
b = 2 // 0..0010

a ^= b // a = 0..0011
b ^= a // b = 0..0001 (ex a)
a ^= b // a = 0..0010 (ex b)

MrC (Member)
Newbie

Messaggi: 19
Iscritto: 28/11/2009

Postato alle 22:02
Venerdì, 29/01/2010

CMQ una cosa semplice per le combianzioni l'avevo fatta, ma mi sono sempre scordato di postarla 8-|

Spero possa essere utile anche ai posteri ( forse in rete c'è di meglio ) :rofl:

Codice sorgente - presumibilmente C++

#include <stdio.h>
#include <malloc.h>
#include <string.h>
 
char *buf;
unsigned long int flevel = 0;
unsigned long int vsize = 0;
 
void combine( const char v[], unsigned long int s, unsigned long int k)
{
  if( flevel==0 ){
    if( (k > vsize) || (k == 0) || (vsize == 0) ){
       printf("\nCan't combine %lu object in group of %lu.",vsize,k);
       return;
    }
    s = 0;
    buf = (char *)malloc(sizeof(char)*k);
  }
 
  flevel++;
 
  int i = s;
  if( k != vsize )
  {
    for(;i<k;i++){
      buf[flevel-1] = v[i];
      combine( v, i+1 , k+1 );
    }
  }
  else
  {
    for(;i<k;i++)
    {
      printf("\n");
      int g=0;
      for(;g<(flevel-1);g++)
        printf("%c",buf[g]);
 
      printf("%c",v[i]);
    }
  }
  
  flevel--;
  if( flevel == 0 )
    free( buf );
}
 
double fatt( unsigned long int n ){
  
  double ret = n;
  
  while( (--n) > 1 )
    ret *= n;
  
  return ret;
}
 
double n_su_k( unsigned long int n, unsigned long int k )
{
  if( k > n )
    return 0;
 
  if( (n==0) || (k==0) )
    return 1;
 
  if( n == k )
    return 1;
 
  return fatt(n)/(fatt(k)*fatt(n-k));
}
 
int main( int argc, char *argv[])
{
 
  if( argc < 3 ){
    printf("Usage: %s string_to_combine groups_length",argv[1]);
    return;
  }
 
  vsize = strlen( argv[1] );
  unsigned long int k = atol( argv[2] );
  
  if( k > vsize ){
    printf("\nCan't combine %lu object in group of %lu.",vsize,k);
    return;
  }
  
  unsigned long int kcomb = 1 + vsize - k;
  
  printf("\n---------------------");
  combine( argv[1], 0, kcomb );
  printf("\n---------------------\n");
  
  printf("Total number (%lu on %lu) = %.0lf\n\n",vsize,k,n_su_k(vsize,k));
}

Pagine: [ 1 2 ]