Différences entre les versions de « Quicky Denombrement »

De Wiki LOGre
Aller à la navigation Aller à la recherche
Ligne 1 : Ligne 1 :
== Introduction ==
== Introduction ==


Dans le cadre d'une application je dois connaitre le nombre d arrangements possibles respectant certaines contraintes.
Dans le cadre d'une application je dois connaitre le nombre d arrangements possibles respectant certaines contraintes.<br/>
 
Il est simple d implémenter un algorithme qui génère toutes les solutions et de compter le nombre de solutions obtenues.<br/>
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.<br/>
 
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<br/>
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


== Le problème ==
== Le problème ==

Version du 21 octobre 2014 à 09:46

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]

Algorithme generant 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 ;
}