IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

Générer les partitions d'un ensemble à exactement k blocs.


Sujet :

C++

  1. #1
    Membre averti Avatar de Seabirds
    Homme Profil pro
    Post-doctoral fellow
    Inscrit en
    avril 2015
    Messages
    271
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Post-doctoral fellow
    Secteur : Agroalimentaire - Agriculture

    Informations forums :
    Inscription : avril 2015
    Messages : 271
    Points : 330
    Points
    330
    Par défaut Générer les partitions d'un ensemble à exactement k blocs.
    Bonjour à toutes et à tous !

    J'aurais besoin de générer toutes les partitions d'un ensemble en exactement k blocs.
    Par exemple, les partitions à deux blocs de l'ensemble {1,2,3} seraient :
    12|3
    1|23
    2|13

    Un algorithme adapté est évoqué à la page 64 du livre de Knuth "Art of Computer Programming, volume 4, fascicle 3", et décrit à la page 127 dans la réponse à la question 17 de la section 7.2.1.5 (les numéros de page peuvent varier suivant les éditions). Bien que dans mon édition l'algorithme ne soit pas numéroté, il semble être connu sous le nom d'algorithme U.
    Ma question avant de ré-implémenter l'algorithme est de savoir si une implémentation en C++ existe déjà. Je n'arrive pas à le trouver sur le web. Je l'ai trouvé en python ici, et en ruby ici. L'auriez-vous un jour aperçu quelque part en vagabondage dans une bibliothèque ?

    En vous remerciant chaleureusement,
    Le débutant, lui, ignore qu'il ignore à ce point, il est fier de ses premiers succès, bien plus qu'il n'est conscient de l'étendue de ce qu'il ne sait pas, dès qu'il progresse en revanche, dès que s'accroît ce qu'il sait, il commence à saisir tout ce qui manque encore à son savoir. Qui sait peu ignore aussi très peu. [Roger Pol-Droit]
    Github
    Mon tout premier projet: une bibliothèque de simulation de génétique des populations

  2. #2
    Expert éminent sénior

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    juin 2007
    Messages
    5 154
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : juin 2007
    Messages : 5 154
    Points : 16 967
    Points
    16 967
    Par défaut
    a priori, pas dans la STL ni dans boost.

    Pour avoir déjà travaillé sur des calculs de partitions, je ne pense pas que ton problème soit difficile à coder, pour peu que tu prennes une représentation correcte d'une partition.

    Supposons que tu produises pour {1,2,3,4} la partition { {1,3},{2,4} }la source de l'algorithme peut être n'importe quoi, tant que tu peux avoir deux itérateurs (begin et end...)

    en sortie, tu peux avoir:
    • une liste de numéro de bloc: {1,2,1,2}
    • la liste re-triée et les frontieres: {1,3,2,4} et {2,4} (les fins de bloc étant le début du suivant.)
    • une liste de bloc (sous forme de vecteurs/listes) { {1,3},{2,4} } (std::list<std::vector<T>>)

    La différence sera surtout dans la manière d'utiliser le résultat, et au final, dans la manière de le produire.

    Si tu dois le réimplémenter, essaye autant que possible de te servir de <algorithm>.
    Mes principes de bases du codeur qui veut pouvoir dormir:
    • Une variable de moins est une source d'erreur en moins.
    • Un pointeur de moins est une montagne d'erreurs en moins.
    • Un copier-coller, ça doit se justifier... Deux, c'est un de trop.
    • jamais signifie "sauf si j'ai passé trois jours à prouver que je peux".
    • La plus sotte des questions est celle qu'on ne pose pas.
    Pour faire des graphes, essayez yEd.
    le ter nel est le titre porté par un de mes personnages de jeu de rôle

  3. #3
    Membre averti Avatar de Seabirds
    Homme Profil pro
    Post-doctoral fellow
    Inscrit en
    avril 2015
    Messages
    271
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Post-doctoral fellow
    Secteur : Agroalimentaire - Agriculture

    Informations forums :
    Inscription : avril 2015
    Messages : 271
    Points : 330
    Points
    330
    Par défaut
    Merci pour ta réponse ! Comme j'ai toujours rien trouvé, je vais faire comme tu conseilles !
    Erreur de typographie ou le an class = "br0" manque cruellement à ma culture ?
    Le débutant, lui, ignore qu'il ignore à ce point, il est fier de ses premiers succès, bien plus qu'il n'est conscient de l'étendue de ce qu'il ne sait pas, dès qu'il progresse en revanche, dès que s'accroît ce qu'il sait, il commence à saisir tout ce qui manque encore à son savoir. Qui sait peu ignore aussi très peu. [Roger Pol-Droit]
    Github
    Mon tout premier projet: une bibliothèque de simulation de génétique des populations

  4. #4
    Expert éminent sénior

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    juin 2007
    Messages
    5 154
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : juin 2007
    Messages : 5 154
    Points : 16 967
    Points
    16 967
    Par défaut
    c'est un bug , c'est la balise c pour faire du "code inline" qui ne semble pas marcher quand on commence par une accolade
    Mes principes de bases du codeur qui veut pouvoir dormir:
    • Une variable de moins est une source d'erreur en moins.
    • Un pointeur de moins est une montagne d'erreurs en moins.
    • Un copier-coller, ça doit se justifier... Deux, c'est un de trop.
    • jamais signifie "sauf si j'ai passé trois jours à prouver que je peux".
    • La plus sotte des questions est celle qu'on ne pose pas.
    Pour faire des graphes, essayez yEd.
    le ter nel est le titre porté par un de mes personnages de jeu de rôle

  5. #5
    Membre averti Avatar de Seabirds
    Homme Profil pro
    Post-doctoral fellow
    Inscrit en
    avril 2015
    Messages
    271
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Post-doctoral fellow
    Secteur : Agroalimentaire - Agriculture

    Informations forums :
    Inscription : avril 2015
    Messages : 271
    Points : 330
    Points
    330
    Par défaut
    Un peu d'eau a coulé sous les ponts, mais finalement j'ai pris le temps de m'y mettre. Pour ce que ça vaut, si ça peut servir à quelqu'un :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    #include <vector>
    #include <numeric>
    #include <string>
    #include <iostream>
    #include <algorithm>
    #include <iterator>
     
    template <typename T>
    std::ostream& operator<< (std::ostream& out, const std::vector<T>& v) {
      if ( !v.empty() ) {
        out << '[';
        std::copy (v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
        out << "\b\b]";
      }
      return out;
    }
     
    class Partitioner
    {
    private:
     
    	using RGS_type = std::vector<unsigned int>; // Restricted Growth String
    	using id_type = unsigned int;
    	using set_type = std::vector<id_type>;
     
    	RGS_type a;
    	std::vector<RGS_type> m_partitions;
    	set_type m_set;
     
    	void visit(){
    		m_partitions.push_back(a);
    	}
     
    	void f(unsigned int mu, unsigned int nu, unsigned int sigma){
    		if(mu == 2){
    			visit();
    		}else{
    			f(mu-1, nu-1, (mu+sigma)%2);
    		}
     
    		if(nu == mu+1){
    			a[mu] = mu -1;
    			visit();
    			while(a[nu] > 0){
    				a[nu] = a[nu] - 1;
    				visit();
    			}
    		}else if(nu > mu + 1){
    			if((mu + sigma)%2 == 1){
    				a[nu - 1] = mu - 1;
    			}else{
    				a[mu] = mu -1;
    			}
     
    			if( (a[nu] + sigma) %2 == 1){
    				b(mu, nu - 1, 0);
    			}else{
    				f(mu, nu  -1, 0);
    			}
     
    			while(a[nu] > 0){
    				a[nu] = a[nu] - 1;
    				if( (a[nu] + sigma) %2 == 1){
    					b(mu, nu - 1, 0);
    				}else{
    					f(mu, nu - 1, 0);
    				}
    			}
    		}
    	}
     
    	void b(unsigned int mu, unsigned int nu, unsigned int sigma){
    		if(nu == mu + 1){
    			while( a[nu] < mu - 1){
    				visit();
    				a[nu] = a[nu] + 1;
    			}
    			visit();
    			a[mu] = 0;
    		}else if( nu > mu + 1){
    			if( (a[nu] + sigma) %2 == 1){
    				f(mu, nu - 1, 0);
    			}else{
    				b(mu, nu -1, 0);
    			}
     
    			while( a[nu] < mu -1 ){
    				a[nu] = a[nu] + 1;
    				if( (a[nu] + sigma) %2 == 1){
    					f(mu, nu - 1, 0);
    				}else{
    					b(mu, nu - 1, 0);
    				}
    			}
     
    			if( (mu + sigma) %2 == 1){
    				a[nu - 1] = 0;
    			}else{
    				a[mu] = 0;
    			}
    		}
     
    		if(mu == 2) {
    			visit();
    		}else{
    			b(mu -1, nu-1, (mu +sigma)%2);
    		}
    	}
     
    	template<typename T>
    	set_type enumerate(T const& set){
    	    std::vector<id_type> v(set.size());
    	    std::iota(v.begin(), v.end(), 1);
    	    return v;
    	}
     
    public:
     
    	template<typename T>
    	Partitioner(T const& set) : m_set(enumerate(set)){}
     
    	Partitioner const& algorithm_u(unsigned int nb_blocks){
    		auto n = m_set.size();
    		a = RGS_type(n+1, 0);
    		for(unsigned int j = 1; j <= nb_blocks; ++j ){ a[n - nb_blocks + j] = j -1;	}
    		f(nb_blocks, n, 0);
    		return *this; 
    	}
     
    	auto begin() const {return m_partitions.begin();}
    	auto end() const {return m_partitions.end();}
    };
    Et là le main :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int main(){
    	std::vector<int> set = {1,2,3,4,5};
    	Partitioner p(set);
    	for(auto const& it : p.algorithm_u(3)){
    		std::cout << it << std::endl;
    	}
     
    	std::cout << std::endl;
     
    	for(auto const& it : p.algorithm_u(4)){
    		std::cout << it << std::endl;
    	}
    }
    Pour mes besoins actuels (ensemble de taille limitée), cette implémentation semble suffire en attendant que j'aille sérieusement m'amuser du côté des coroutines.
    Merci encore leternel !
    Le débutant, lui, ignore qu'il ignore à ce point, il est fier de ses premiers succès, bien plus qu'il n'est conscient de l'étendue de ce qu'il ne sait pas, dès qu'il progresse en revanche, dès que s'accroît ce qu'il sait, il commence à saisir tout ce qui manque encore à son savoir. Qui sait peu ignore aussi très peu. [Roger Pol-Droit]
    Github
    Mon tout premier projet: une bibliothèque de simulation de génétique des populations

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 2
    Dernier message: 17/01/2016, 14h24
  2. [À télécharger] Générer les partitions d'un ensemble
    Par SfJ5Rpw8 dans le forum Vos téléchargements VB6
    Réponses: 0
    Dernier message: 14/11/2010, 18h21
  3. générer toutes les permutations d'un ensemble fini d'éléments
    Par Didier77 dans le forum Algorithmes et structures de données
    Réponses: 17
    Dernier message: 25/09/2007, 07h34
  4. [Visual FoxPro 9] Générer les disquettes d'installation
    Par petrone dans le forum Autres langages
    Réponses: 1
    Dernier message: 04/01/2005, 11h54
  5. [VB6] partitions d'un ensemble
    Par perduuu dans le forum VB 6 et antérieur
    Réponses: 6
    Dernier message: 13/09/2004, 16h21

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo