diffsym.cpp

// $Id: diffsym.cpp,v 1.5 2006/04/25 12:45:20 mstorti Exp $

/* COMIENZO DE DESCRIPCION 

   __USE_WIKI__
   Dada una lista de conjuntos de enteros 
   #list< set<int> > l# escribir una funci\'on 
   #void diffsym(list< set<int> > &L, set<int> &ad)# 
   que retorna en #ad# el conjunto de los elementos que
   pertenecen a uno y s\'olo uno de los conjuntos de #L#. 
   Por ejemplo, si #L = ({1,2,3},{2,4,5},{4,6})# entonces
   #ad# debe ser #{1,3,5,6}#. Notar que si el n\'umero
   de conjuntos en #l# es 2 y los llamamos #A# y #B#, 
   entonces debe retornar #ad = (A-B) union (B-A)#. 
   [Tomado en el 3er parcial 23/6/2005]. 
   keywords: conjunto

   FIN DE DESCRIPCION */

#include <cmath>
#include <set>
#include <list>
#include <algorithm>
#include "./util.h"

using namespace std;

void print(const set<int> &s,
	   const char *t=NULL) {
  if (t) printf("%s",t);
  set<int>::iterator q = s.begin();
  while (q!=s.end()) printf("%d ",*q++);
  printf("\n");
}

//    Un algoritmo posible es recorrer todos los elementos
//    #x# que pertenecen a alg\'un conjunto de #l# y contar
//    en cuantos elementos de #l# est\'a (debe estar en al 
//    menos uno). El elemento es insertado en #ad# s\'olo
//    si el conteo da exactamente 1. 
//---:---<*>---:---<*>---:---<*>---:---<*>---:---<*>
void diffsym(list< set<int> > &l,set<int> &ad) {
  list< set<int> >::iterator q = l.begin();
  while (q!=l.end()) {
    set<int> &s = *q;
    set<int>::iterator r = s.begin();
    while (r!=s.end()) {
      int count = 0;
      list< set<int> >::iterator w = l.begin();
      while (w!=l.end()) {
	if (w->find(*r) != w->end()) count++;
	if (count>=2) break;
	w++;
      }
      if (count==1) ad.insert(*r);
      r++;
    }
    q++;
  }
}

//---:---<*>---:---<*>---:---<*>---:---<*>---:---<*>
// Otro algoritmo, basado en funciones binarias
// Notar que en el caso de tres conjuntos si:
// S=diffsym(A,B) y
// U= A union B,
// entonces:
// diffsym(A,B,C) = (S-C) \cup (C-U). 
// Esto vale en general para cualquier n\'umero de conjuntos, de manera
// que podemos utilizar el siguiente lazo
// L = lista de conjuntos, S=U=<conjunto-vacio>
// FOR Q en la lista de conjuntos de L
// S = (S-Q) union (Q-U)
// U = U union Q
// Al terminar el lazo, S es la diferencia sim\'etrica buscada. 
void diffsym2(list< set<int> > &l,
		   set<int> &all_diff) {
  all_diff.clear();
  set<int> all_union,s1,s2;
  list< set<int> >::iterator 
    q = l.begin();
  while (q!=l.end()) {
    s2.clear();
    set_difference(all_diff.begin(),all_diff.end(),
		   q->begin(),q->end(),
		   inserter(s2,s2.begin()));
    all_diff = s2;

    set_difference(q->begin(),q->end(),
		   all_union.begin(),all_union.end(),
		   inserter(all_diff,all_diff.begin()));

    s1.clear();
    set_union(q->begin(),q->end(),
	      all_union.begin(),all_union.end(),
	      inserter(s1,s1.begin()));
    all_union = s1;
    q++;
  }
}

//---:---<*>---:---<*>---:---<*>---:---<*>---:---<*>
void make_random_set(set<int> &s,
		     int m,int n,int N) {
  double lambda = 1.0/(m+1);	// Probability of stopping
  s.clear();
  while(1) {
    if (drand()<lambda) break;
    int w = rand() % N;
    s.insert(w);
  }
}

// -------------------------------------------------------------------
int main () {
  int N = 20;		  // Max nbr of elements in all sets
  int m = 5;			// Nbr oe elements in each set
  int n = 5;			// nbr of sets
  list< set<int> > l;
  double lambda = 1.0/(m+1);	// Probability of stopping
  double sav = 0.0;
  for (int k=0; k<n; k++) {
    l.push_back(set<int>());
    set<int> &s = l.back();
    make_random_set(s,m,n,N);
    printf("set[%d]: ",k);
    print(s);
    sav += s.size();
  }
  printf("average set size %f\n",sav/n);

  set<int> S;
  S.clear();
  diffsym(l,S);
  print(S,"using diffsym():");

  S.clear();
  diffsym2(l,S);
  print(S,"using diffsym2():");

}