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

Version imprimable

23/08/2016, 14h37
Seabirds

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,
23/08/2016, 16h47
ternel
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>.
23/08/2016, 17h06
Seabirds

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 ?
23/08/2016, 17h08
ternel

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

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:

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:

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 ! :D