Quicky Denombrement

De Wiki LOGre
Aller à : navigation, rechercher


Introduction

Dans le cadre d'une application je dois connaitre le nombre d arrangements possibles respectant certaines contraintes.
Il est simple d implémenter un algorithme qui génère toutes les solutions et de compter le nombre de solutions obtenues.
Cette approche a pour inconvénient de nécessiter un très grand nombre de calculs des que le nombre d entrées du problème augmente.
Le but est de trouver un moyen d'obtenir le nombre de solutions possibles sans avoir a les énumérer de la meme facon que !n donne le nombre de permutations de n elements sans avoir besoin de les lister

Le problème

  • Je dispose de 4 listes tries d elements contenant au maximum M elements.
  • La liste liste_i ( 0 <= i < 4) contient Ti elements tels que Ti <= M avec pour tout k : liste_i[k] < liste_i[k+1] et k < Ti

Je voudrais connaitre le nombre d'arrangements qu il est possible de faire en prenant un element de chaque liste avec comme contrainte qu un element ne puisse pas etre selectionne dans plus d une liste a la fois :
R = {liste_a[V] , liste_b[X], liste_c [Y], liste_d[Z] } tel que

  • 0 <= a <4 , 0 <= b < 4 , 0 <= c <4 , 0 <= d < 4 avec a != b != c != d
  • 0<= V < Ta , 0 <= X < Tb , 0 <= Y < Tc , 0 <= Z < Td
  • liste_a[V]  != liste_b[X] != liste_c [Y] != liste_d[Z]

Exemple

  • Liste_1 = {1,2,3,4}
  • Liste_2 = {2,4}
  • Liste_3 = {1,3,5}
  • Liste_4 = {2,5}

Les solutions respectant les contraintes sont au nombre de 12 et sont les suivantes :

  • [1,2,3,5] [1,4,3,2] [1,4,3,5] [1,4,5,2] [2,4,1,5] [2,4,3,5] [3,2,1,5] [3,4,1,2] [3,4,1,5] [3,4,5,2] [4,2,1,5] [4,2,3,5]

Les solutions ne respectant pas les contraintes sont au nombre de 18 et sont les suivantes :

  • [1,2,1,2] [1,2,1,5] [1,2,3,2] [1,2,5,2] [1,4,1,2] [1,4,1,5] [2,4,1,2] [2,4,3,2] [2,4,5,2] [3,2,1,2] [3,2,3,2] [3,2,3,5] [3,2,5,2] [3,4,3,2] [3,4,3,5] [4,2,1,2] [4,2,3,2] [4,2,5,2]

Algorithme générant les solutions

Voici un algorithme en C++ permettant d obtenir toutes les solutions :

#include <set>
#include <iostream>
#include <inttypes.h>
 
const uint32_t construct_count(const std::set<uint32_t> & p_list1,
                               const std::set<uint32_t> & p_list2,
                               const std::set<uint32_t> & p_list3,
                               const std::set<uint32_t> & p_list4
                               )
{
  unsigned int l_result = 0;
  for(auto l_iter1 : p_list1)
    {
      for(auto l_iter2 : p_list2)
        {
          if(l_iter2 != l_iter1)
            {
              for(auto l_iter3 : p_list3)
                {
                  if(l_iter3 != l_iter2 && l_iter3 != l_iter1)
                    {
                      for(auto l_iter4 : p_list4)
                        {
                          if(l_iter4 != l_iter3 && l_iter4 != l_iter2 && l_iter4 != l_iter1)
                            {
                              ++l_result;
                            }
                        }
                    }
                }
            }
        }
    }
  return l_result;
}
 
int main(void)
{
  std::set<uint32_t> l_list1 = {1,2,3,4};
  std::set<uint32_t> l_list2 = {2,4};
  std::set<uint32_t> l_list3 = {1,3,5};
  std::set<uint32_t> l_list4 = {2,5};
 
  std::cout << "Enumerated result = " << construct_count(l_list1, l_list2, l_list3, l_list4) << std::endl ;
}

Du fait des 4 boucles for imbriquees, le temps d execution va augmenter tres vite si la longueur des listes augmente

Algorithme calculant le nombre de solutions

Le but de cet algorithme est de fournir directement le nombre de solutions sans avoir a les énumérer de façon a ce que son temps d exécution augmente peu avec la taille des listes.

Rappels

  • Intersection de deux listes : liste des éléments appartenant aux deux listes
    • Liste_1 && Liste_2 : {2,4}
  • Union de deux listes : liste des éléments appartenant a l une des deux listes
    • Liste_3 || Liste_4 : {1,2,3,5}
  • Différence de deux listes : Liste des éléments appartenant a Liste_1 mais pas a Liste_2
    • Liste_1 - Liste_2 : {1,3}
  • Combinaison de deux listes : Liste des combinaisons obtenues en prenant le premier 1 élément dans la liste 1 et le 2eme élément pris dans la liste 2
    • Liste_1 * Liste_2 : { [1 2],[1 4],[2 2],[2 4],[3 2],[3 4],[4 2],[4 4] }
  • Cardinal d une liste : nombre d éléments de la liste
    • Card(Liste_1) = 4
  • Combinaisons de p éléments pris parmi n : Cnp
    • nCp = (n!) / ( (n-p)! * p!)

Principe

Soit f la fonction qui regroupe les 4 listes en respectant les contraintes et f' la fonction qui regroupe deux listes en respectant les contraintes
On cherche Card(f(Liste_1,Liste_2,Liste_3,Liste_4)) renvoyant le nombre de combinaisons possibles tout en respectant les contraintes.
Nous allons essayer de décomposer le problème de la façon suivante: f(Liste_1,Liste_2,Liste_3,Liste_4) = f'(f'(Liste_1,Liste_2),f'(Liste_3,Liste_4))

Combinaison de deux listes

Lors de la combinaison de deux listes, les combinaisons ne respectant pas la contrainte sont celles ou le même terme est pris dans liste 1 et la liste 2
Par exemple pour Liste_1 * Liste_2 : { [1 2],[1 4],[2 2],[2 4],[3 2],[3 4],[4 2],[4 4] } les items [2 2] [4 4] sont invalides
Les seuls doublons possibles sont ceux constitues des éléments apparaissant dans les 2 listes, on a donc
Nombre de combinaisons(Liste_i,Liste_j) = Card(Liste_i * Liste_j) - Card(Liste_i && Liste_j)
Soit Nombre de combinaisons(Liste_i,Liste_j) = Card(Liste_i) * Card(Liste_j) - Card(Liste_i && Liste_j)

Le problème ayant 4 listes en entrées on peut donc utiliser cette formule pour grouper les listes 2 par 2, par exemple Liste_1 Liste_2 et Liste_3 Liste_4
Il reste a calculer le nombre de résultats de ces deux regroupements

Combinaison des regroupements de deux listes

Dans le cas de notre exemple f'(Liste_1,Liste_2) donne {[1 2],[1 4],[2 4],[3 2],[3 4],[4 2]} et f'(Liste_3,Liste_4) donne {[1 2],[1 5],[3 2],[3 5],[5 2]}
Certains regroupements tels que [1 2 1 2] ou [3 4 3 5] ne respectent pas les contraintes il faut donc les éliminer du calcul
On voit que les combinaisons posant problèmes sont celles regroupant des termes dont au moins un des éléments se trouve dans f'(Liste_1,Liste_2) et f'(Liste_3,Liste_4)
c est a dire : (Liste_1 || Liste_2) && (Liste_3 || Liste_4) soit dans notre exemple ({1,2,3,4) || {2,4}) && ({1,3,5} || {2,5}) = {1,2,3,4} && {1,2,3,5} = {1,2,3}
On a donc f(Liste_1,Liste_2,Liste_3,Liste_4) = f'(f'(Liste_1,Liste_2),f'(Liste_3,Liste_4)) = f'(Liste_1,Liste_2) * f'(Liste_3,Liste_4) - {Liste des termes invalides}
Dans notre exemple Card(f(Liste_1,Liste_2,Liste_3,Liste_4) = Card(f'(Liste_1,Liste_2) * Card(f'(Liste_3,Liste_4)) - Card({Liste des termes invalides})
Soit Card(f(Liste_1,Liste_2,Liste_3,Liste_4) = 6 * 5 - Card({Liste des termes invalides})

Calcul des termes invalides

Il s agit de calculer les termes entrant dans la composition des combinaisons invalides. Pour lister les termes invalides une et une seule fois il faut distinguer les combinaisons ou un seul élément apparait en double : [3 4 3 5] de ceux ou deux éléments apparaissent en double [1 2 1 2]
Pour chaque élément de (Liste_1 || Liste_2) && (Liste_3 || Liste_4) on liste les combinaisons ou un seul élément de cette liste n apparait:
(Liste_i - (Liste_1 || Liste_2) && (Liste_3 || Liste_4)) si l élément apparait dans la liste regroupée avec Liste_i, a répéter pour les 4 listes
Dans le cas de notre exemple on a donc

  • 1 terme avec {1} : [1 4] dans f'(Liste_1,Liste_2) et 1 terme avec {1} : [1 5] dans f'(Liste_3,Liste_4)
  • 2 termes avec {2} : [2 4] [4 2] dans f'(Liste_1,Liste_2) et 1 terme avec {2} : [5 2 ] dans f'(Liste_3,Liste_4)
  • 1 termes avec {3} : [ 3 4] dans f'(Liste_1,Liste_2) et 1 terme avec {3} : [3 5] dans f'(Liste_3,Liste_4)

Les différentes combinaisons possibles de deux éléments tires de (Liste_1 || Liste_2) && (Liste_3 || Liste_4) est donne par nC2 = (n * (n - 1))/2 avec n = Card((Liste_1 || Liste_2) && (Liste_3 || Liste_4))
Dans notre exemple 3C2 = 3 ce qui correspond a [1 3] [1 2] [2 3]
Pour chaque combinaison il est facile de calculer le nombre de termes en testant l appartenance de chacun des éléments aux listes ce qui donne pour notre exemple

  • 1 terme [1 2] dans f'(Liste_1,Liste_2) et 1 terme avec [1 2] dans f'(Liste_3,Liste_4)
  • 1 terme [2 3] dans f'(Liste_1,Liste_2) et 1 terme avec [2 3] dans f'(Liste_3,Liste_4)
  • 0 terme [1 3] dans f'(Liste_1,Liste_2) et 0 terme avec [1 3] dans f'(Liste_3,Liste_4)
Calcul du nombre de combinaisons invalides

En calculant le nombre de regroupements entre les termes simples et les termes doubles ou les éléments se répètent il devient facile de compter le nombre de combinaisons invalides:

  • terme avec {1} dans f'(Liste_1,Liste_2) regroupes avec terme avec [1 2] dans f'(Liste_3,Liste_4) = 1 * 1 = 1
  • terme avec [1 2] dans f'(Liste_1,Liste_1) regroupes avec terme avec {1} dans f'(Liste_3,Liste_4) = 1 * 1 = 1
  • terme avec {1} dans f'(Liste_1,Liste_2) regroupes avec terme avec {1} dans f'(Liste_3,Liste_4) = 1 * 1 = 1
  • terme avec [1 2] dans f'(Liste_1,Liste_2) regroupes avec terme avec [1 2] dans f'(Liste_3,Liste_4) = 1 * 1 = 1
  • etc etc

On obtient un total de 18 termes invalides

calcul final

Soit Card(f(Liste_1,Liste_2,Liste_3,Liste_4) = 30 - 18 = 12

Reflexion sur les regroupements

On a vu que la plupart des calculs sont en complexite O(n) de la taille des listes excepte le calcul du nombre de termes invalides qui est en O(n*n) avec n la taille de (Liste_1 || Liste_2) && (Liste_3 || Liste_4) il peut donc être intéressant de regrouper les listes 2 par 2 de facon a minimiser cette taille ce qui donne les possibilités suivantes:

  • (Liste_1 || Liste_2) && (Liste_3 || Liste_4) ce qui donne pour notre exemple {1,2,3}
  • (Liste_1 || Liste_3) && (Liste_2 || Liste_4) ce qui donne pour notre exemple {2,4,5}
  • (Liste_1 || Liste_4) && (Liste_2 || Liste_3) ce qui donne pour notre exemple {1,2,3,4,5}

Ce calcul ayant une complexité en O(n) alors que l énumeration des termes invalides est en O(n*n) il est intéressant de choisir la bonne combinaison

Implementation

L`implementation est basee sur C++ et les std::set dont l API fournit des methodes permettant le calcul d'unions d intersections differences etc

#include <set>
#include <iostream>
#include <inttypes.h>
#include <algorithm>
#include <map>
 
const uint32_t Cn2(const uint32_t & p_n)
{
  return (p_n * (p_n - 1)) / 2;
}
 
const unsigned int count_double_terms(const uint32_t & p_term1,
                                      const uint32_t & p_term2,
                                      const std::set<uint32_t> & p_list1,
                                      const std::set<uint32_t> & p_list2)
{
  return (p_list1.count(p_term1) && p_list2.count(p_term2)) + (p_list2.count(p_term1) && p_list1.count(p_term2));
}
 
const unsigned int count_single_terms(const uint32_t & p_term,
                                      const std::set<uint32_t> & p_list1,
                                      const std::set<uint32_t> & p_list2,
                                      const std::vector<uint32_t> & p_intersec)
{
  unsigned int l_result = 0;
  std::vector<uint32_t> l_purged_list1(p_list1.size());
  std::vector<uint32_t>::iterator l_it;
  l_it = std::set_difference(p_list1.begin(),p_list1.end(),p_intersec.begin(),p_intersec.end(),l_purged_list1.begin());
  l_purged_list1.resize(l_it-l_purged_list1.begin());
 
  std::vector<uint32_t> l_purged_list2(p_list2.size());
  l_it = std::set_difference(p_list2.begin(),p_list2.end(),p_intersec.begin(),p_intersec.end(),l_purged_list2.begin());
  l_purged_list2.resize(l_it-l_purged_list2.begin());
 
  if(p_list1.count(p_term)) l_result += l_purged_list2.size();
  if(p_list2.count(p_term)) l_result += l_purged_list1.size();
  return l_result;
}
 
const uint32_t compute_count(const std::set<uint32_t> & p_list1,
                             const std::set<uint32_t> & p_list2,
                             const std::set<uint32_t> & p_list3,
                             const std::set<uint32_t> & p_list4
                             )
{
  unsigned int l_result = 0;
 
  std::vector<uint32_t>::iterator l_it;
 
  // calcul des regroupements de deux listes 
  unsigned int l_max = 0;
  std::vector<uint32_t> l_union_1_2(p_list1.size()+p_list2.size());
  l_it = std::set_union (p_list1.begin(),p_list1.end(),p_list2.begin(),p_list2.end(), l_union_1_2.begin());
  l_union_1_2.resize(l_it-l_union_1_2.begin());
  if(l_max < l_union_1_2.size()) l_max = l_union_1_2.size();
 
  std::vector<uint32_t> l_union_1_3(p_list1.size()+p_list3.size());
  l_it = std::set_union (p_list1.begin(),p_list1.end(),p_list3.begin(),p_list3.end(), l_union_1_3.begin());
  l_union_1_3.resize(l_it-l_union_1_3.begin());
  if(l_max < l_union_1_3.size()) l_max = l_union_1_3.size();
 
  std::vector<uint32_t> l_union_1_4(p_list1.size()+p_list4.size());
  l_it = std::set_union (p_list1.begin(),p_list1.end(),p_list4.begin(),p_list4.end(), l_union_1_4.begin());
  l_union_1_4.resize(l_it-l_union_1_4.begin());
  if(l_max < l_union_1_4.size()) l_max = l_union_1_4.size();
 
  std::vector<uint32_t> l_union_2_3(p_list2.size()+p_list3.size());
  l_it = std::set_union (p_list2.begin(),p_list2.end(),p_list3.begin(),p_list3.end(), l_union_2_3.begin());
  l_union_2_3.resize(l_it-l_union_2_3.begin());
  if(l_max < l_union_2_3.size()) l_max = l_union_2_3.size();
 
  std::vector<uint32_t> l_union_2_4(p_list2.size()+p_list4.size());
  l_it = std::set_union (p_list2.begin(),p_list2.end(),p_list4.begin(),p_list4.end(), l_union_2_4.begin());
  l_union_2_4.resize(l_it-l_union_2_4.begin());
  if(l_max < l_union_2_4.size()) l_max = l_union_2_4.size();
 
  std::vector<uint32_t> l_union_3_4(p_list3.size()+p_list4.size());
  l_it = std::set_union (p_list3.begin(),p_list3.end(),p_list4.begin(),p_list4.end(), l_union_3_4.begin());
  l_union_3_4.resize(l_it-l_union_3_4.begin());
  if(l_max < l_union_3_4.size()) l_max = l_union_3_4.size();
 
  // calcul des 3 intersections de regroupement pour choisir la meilleure intersection
  unsigned int l_min = l_max;
  unsigned int l_choice = 0;
 
  std::vector<uint32_t> l_intersection_1_2_3_4(l_max);
  l_it = std::set_intersection (l_union_1_2.begin(),l_union_1_2.end(),l_union_3_4.begin(),l_union_3_4.end(), l_intersection_1_2_3_4.begin());
  l_intersection_1_2_3_4.resize(l_it-l_intersection_1_2_3_4.begin());
  if(l_intersection_1_2_3_4.size() < l_min ) 
    {
      l_min = l_intersection_1_2_3_4.size();
    }
 
  std::vector<uint32_t> l_intersection_1_3_2_4(l_max);
  l_it = std::set_intersection (l_union_1_3.begin(),l_union_1_3.end(),l_union_2_4.begin(),l_union_2_4.end(), l_intersection_1_3_2_4.begin());
  l_intersection_1_3_2_4.resize(l_it-l_intersection_1_3_2_4.begin());
  if(l_intersection_1_3_2_4.size() < l_min ) 
    {
      l_min = l_intersection_1_3_2_4.size();
      l_choice = 1;
    }
 
  std::vector<uint32_t> l_intersection_1_4_2_3(l_max);
  l_it = std::set_intersection (l_union_1_4.begin(),l_union_1_4.end(),l_union_2_3.begin(),l_union_2_3.end(), l_intersection_1_4_2_3.begin());
  l_intersection_1_4_2_3.resize(l_it-l_intersection_1_4_2_3.begin());
  if(l_intersection_1_4_2_3.size() < l_min ) 
    {
      l_min = l_intersection_1_4_2_3.size();
      l_choice = 2;
    }
 
  // On se ramene au cas (Liste_1,Liste_2) (Liste_3,Liste_4) par des alias
  const std::set<uint32_t> & l_list1_bis = p_list1;
  const std::set<uint32_t> & l_list2_bis = (l_choice == 0 ? p_list2 : ( l_choice == 1 ? p_list3 : p_list4));
  const std::set<uint32_t> & l_list3_bis = (l_choice == 0 ? p_list3 : p_list2);
  const std::set<uint32_t> & l_list4_bis = (l_choice == 2 ? p_list3 : p_list4);
  const std::vector<uint32_t> & l_intersect_1_2_3_4_bis = (l_choice == 0 ? l_intersection_1_2_3_4 : l_choice == 1 ? l_intersection_1_3_2_4 : l_intersection_1_4_2_3);
 
  // Calcul des intersections pour preparer la generation des termes simples
  std::vector<uint32_t> l_intersection_1_2(l_list1_bis.size()+l_list2_bis.size());
  l_it = std::set_intersection (l_list1_bis.begin(),l_list1_bis.end(),l_list2_bis.begin(),l_list2_bis.end(), l_intersection_1_2.begin());
  l_intersection_1_2.resize(l_it-l_intersection_1_2.begin());
 
  std::vector<uint32_t> l_intersection_3_4(l_list3_bis.size()+l_list4_bis.size());
  l_it = std::set_intersection (l_list3_bis.begin(),l_list3_bis.end(),l_list4_bis.begin(),l_list4_bis.end(), l_intersection_3_4.begin());
  l_intersection_3_4.resize(l_it-l_intersection_3_4.begin());
 
  // calcul des cardinaux des deux regroupements et du nombre de termes doubles
  unsigned int l_card_1_2 = l_list1_bis.size() * l_list2_bis.size() - l_intersection_1_2.size();
  unsigned int l_card_3_4 = l_list3_bis.size() * l_list4_bis.size() - l_intersection_3_4.size();
  unsigned int l_combin_nb = Cn2(l_intersect_1_2_3_4_bis.size());
 
  l_result = l_card_1_2 * l_card_3_4;
 
  // Variables pour stocker le nombre de termes simples et doubles
  std::pair<unsigned int,unsigned int> * l_single_terms_count = new std::pair<unsigned int,unsigned int>[l_intersect_1_2_3_4_bis.size()];
  std::pair<std::pair<unsigned int,unsigned int>,std::pair<unsigned int, unsigned int> > * l_double_terms_count = new std::pair<std::pair<unsigned int,unsigned int>,std::pair<unsigned int,unsigned int> >[l_combin_nb];
 
  // Stocakge des assocations de terme violant les constraintes
  std::multimap<unsigned int,unsigned int> l_associated_combin;
 
  // Comptage des termes simples et doubles
  unsigned int l_combin_index = 0;
  for(unsigned int l_index = 0 ; l_index < l_intersect_1_2_3_4_bis.size() ; ++l_index)
    {
      l_single_terms_count[l_index] = std::pair<unsigned int,unsigned int>(count_single_terms(l_intersect_1_2_3_4_bis[l_index],l_list1_bis,l_list2_bis,l_intersect_1_2_3_4_bis),
                                                                           count_single_terms(l_intersect_1_2_3_4_bis[l_index],l_list3_bis,l_list4_bis,l_intersect_1_2_3_4_bis));
      for(unsigned int l_index2 = l_index + 1 ; l_index2 < l_intersect_1_2_3_4_bis.size() ; ++l_index2)
        {
	  l_double_terms_count[l_combin_index] = std::pair<std::pair<unsigned int,unsigned int>,std::pair<unsigned int, unsigned int> >(std::pair<unsigned int,unsigned int>(l_intersect_1_2_3_4_bis[l_index],l_intersect_1_2_3_4_bis[l_index2]),std::pair<unsigned int,unsigned int>(count_double_terms(l_intersect_1_2_3_4_bis[l_index],l_intersect_1_2_3_4_bis[l_index2],l_list1_bis,l_list2_bis),count_double_terms(l_intersect_1_2_3_4_bis[l_index],l_intersect_1_2_3_4_bis[l_index2],l_list3_bis,l_list4_bis)));
	  l_associated_combin.insert(std::multimap<unsigned int,unsigned int >::value_type(l_intersect_1_2_3_4_bis[l_index],l_combin_index));
	  l_associated_combin.insert(std::multimap<unsigned int,unsigned int >::value_type(l_intersect_1_2_3_4_bis[l_index2],l_combin_index));
	  ++l_combin_index;
 
        }
    }
 
  // On enleve les termes simples identiques regroupes 
  for(unsigned int l_index = 0 ; l_index < l_intersect_1_2_3_4_bis.size() ; ++l_index)
    {
      l_result -= l_single_terms_count[l_index].first * l_single_terms_count[l_index].second;
    }
  // On enleve les doubles termes identiques regroupes
  for(unsigned int l_index = 0 ; l_index < l_combin_nb ; ++l_index)
    {
      l_result -= l_double_terms_count[l_index].second.first * l_double_terms_count[l_index].second.second;
    }
 
  // On enleve les doubles termes regroupes avec des simples termes
   for(unsigned int l_index = 0 ; l_index < l_intersect_1_2_3_4_bis.size() ; ++l_index)
    {
      if(l_single_terms_count[l_index].first)
	{
	  std::pair<std::multimap<unsigned int,unsigned int>::const_iterator,std::multimap<unsigned int,unsigned int>::const_iterator> l_pair = l_associated_combin.equal_range(l_intersect_1_2_3_4_bis[l_index]);
	  while(l_pair.first != l_pair.second)
	    {
	      l_result -= l_single_terms_count[l_index].first * l_double_terms_count[l_pair.first->second].second.second;
	      ++(l_pair.first);
	    }
	}
      if(l_single_terms_count[l_index].second)
	{
	  std::pair<std::multimap<unsigned int,unsigned int>::const_iterator,std::multimap<unsigned int,unsigned int>::const_iterator> l_pair = l_associated_combin.equal_range(l_intersect_1_2_3_4_bis[l_index]);
	  while(l_pair.first != l_pair.second)
	    {
	      l_result -= l_single_terms_count[l_index].second * l_double_terms_count[l_pair.first->second].second.first;
	      ++(l_pair.first);
	    }
	}
    }   
 
   // On enleve les regroupements de double termes
   for(unsigned int l_index = 0 ; l_index < l_intersect_1_2_3_4_bis.size() ; ++l_index)
    {
      std::pair<std::multimap<unsigned int,unsigned int>::const_iterator,std::multimap<unsigned int,unsigned int>::const_iterator> l_pair = l_associated_combin.equal_range(l_intersect_1_2_3_4_bis[l_index]);
      while(l_pair.first != l_pair.second)
        {
          std::multimap<unsigned int,unsigned int>::const_iterator l_iter2 = l_pair.first;
          ++l_iter2;
          while(l_iter2 != l_pair.second)
            {
              l_result -= l_double_terms_count[l_pair.first->second].second.first * l_double_terms_count[l_iter2->second].second.second;
              l_result -= l_double_terms_count[l_pair.first->second].second.second * l_double_terms_count[l_iter2->second].second.first;
              ++l_iter2;
            }
          ++(l_pair.first);          
        }
    }
 
 
  return l_result;
}
 
int main(void)
{
  std::set<uint32_t> l_list1 = {1,2,3,4};
  std::set<uint32_t> l_list2 = {2,4};
  std::set<uint32_t> l_list3 = {1,3,5};
  std::set<uint32_t> l_list4 = {2,5};
 
  uint32_t l_computed_result = compute_count(l_list1, l_list2, l_list3, l_list4);
  std::cout << "Computed result = " << l_computed_result << std::endl ;
}

Compilation

Avec gcc 4.8.1 :

g++ -o test.exe test.cpp -Wall -ansi -pedantic -g -std=c++11 -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -D__STDC_CONSTANT_MACROS -O3 -DNDEBUG

Resultats

J ai fait tourne les deux algorithmes ( compiles en -O3) sur plusieurs test cases et utilise callgrind pour obtenir le nombre d instructions executees afin de mesurer la complexite a l execution.
Le graphe ci dessous represente les resultats obtenus sachant que la taille de la liste est a peu pres identique pour Liste_1 Liste_2 Liste_3 Liste_4

Nombre d instructions exécutées en fonction de la taille des listes d entrées



On voit que l algorithme enumerant toutes les solutions voit sa complexite augmenter tres vite avec la taille de la liste alors que l algorithme calculant le nombre de solution reste a un niveau de complexite d execution bien plus faible