Ok, adesso le cose mi sono un po' più chiare, anche se non del tutto.
In ogni caso ti dico quello che ho fatto io, poi mi dici tu se c'entra o meno con quello che stavi cercando di fare.
Per prima cosa mi calcolo le partizioni di
n_max, e per farlo non sfrutto ricorsioni o cose del genere, ma mi limito a costruire la partizione successiva partendo da quella corrente sfruttando l'ordine lessicografico e sapendo che la partizione iniziale è data da una sequenza di
n_max "1", mentre quella finale dal solo valore "
n_max".
In questo modo trovo l'elenco
v_p_1 delle partizioni di
n_max in ordine lessicografico, poi riordinando le suddette partizioni ottengo un secondo elenco
v_p_2 che soddisfa il criterio di estrapolazione delle partizioni di
n (con
n minore o uguale a
n_max), da te così descritto:
Per passare da
v_p_1 a
v_p_2 sfrutto un criterio di ordinamento basato in prima istanza sul numero di "1" e in seconda istanza sul numero di elementi delle singole partizioni.
Di seguito il codice in C++:
C++:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
//GENERA LA PARTIZIONE SUCCESSIVA IN ORDINE LESSICOGRAFICO
//LA SINGOLA PARTIZIONE E' IN ORDINE LESSICOGRAFICO INVERSO
//IL VETTORE w CONTIENE L'INDICE, IL NUMERO DI "1" E IL NUMERO DI ELEMENTI DI OGNI PARTIZIONE
vector<unsigned int> partizione_successiva(const unsigned int n_max, const vector<unsigned int> &p, vector<vector<unsigned int>> &w)
{
vector<unsigned int> p_succ;
unsigned int m = 0;
unsigned int i = p.size() - 2;
for(; i && p[i] == p[i - 1]; --i);
for(unsigned int j = 0; j <= i; ++j)
{
p_succ.push_back(p[j]);
m += p_succ.back();
}
for(++p_succ.back(), ++m, i = n_max - m; i; --i)
{
p_succ.push_back(1);
}
w.push_back({(unsigned int)w.size(), n_max - m, (unsigned int)p_succ.size()});
return p_succ;
}
bool funzione_comparazione(const vector<unsigned int> &v_1, const vector<unsigned int> &v_2)
{
return v_2[1] < v_1[1] || v_2[1] == v_1[1] && v_2[2] < v_1[2];
}
//RIORDINA LE PARTIZIONI DI n_max PER RISPETTARE IL CRITERIO DI ESTRAPOLAZIONE DELLE
//PARTIZIONI DI n <= n_max UTILIZZATO IN stampa_2()
vector<vector<unsigned int>> partizioni_ordinate(const vector<vector<unsigned int>> &v_p_1, vector<vector<unsigned int>> &w)
{
vector<vector<unsigned int>> v_p_2;
sort(w.begin(), w.end(), funzione_comparazione);
for(unsigned int i = 0; i < v_p_1.size(); ++i)
{
v_p_2.push_back(v_p_1[w[i][0]]);
}
return v_p_2;
}
void stampa_1(const vector<vector<unsigned int>> &v_p)
{
for(unsigned int i = 0; i < v_p.size(); ++i)
{
cout << "\n " << i + 1 << ":\t";
for(unsigned int j = 0; j < v_p[i].size(); ++j)
{
cout << v_p[i][j] << " ";
}
}
cout << "\n";
}
void stampa_2(const vector<vector<unsigned int>> &v_p_2, const unsigned int n_max, const unsigned int n)
{
if(n && n <= n_max)
{
unsigned int i = 0;
unsigned int j;
unsigned int sum;
do
{
j = sum = 0;
cout << "\n " << i + 1 << ":\t";
do
{
cout << v_p_2[i][j] << " ";
}
while((sum += v_p_2[i][j++]) != n);
}
while(v_p_2[i++][0] != n);
cout << "\n";
}
}
int main()
{
unsigned int n_max = 9;
unsigned int n = 7;
if(n_max)
{
vector<vector<unsigned int>> v_p_1(1, vector<unsigned int>(n_max, 1));
vector<vector<unsigned int>> w(1, {0, n_max, n_max});
for(; v_p_1.back().front() != n_max; v_p_1.push_back(partizione_successiva(n_max, v_p_1.back(), w)));
vector<vector<unsigned int>> v_p_2 = partizioni_ordinate(v_p_1, w);
stampa_1(v_p_1);
stampa_1(v_p_2);
stampa_2(v_p_2, n_max, n);
}
}
Questo invece è l'output, che mostra prima l'elenco delle partizioni di
n_max=9 in ordine lessicografico, poi l'elenco delle partizioni di
n_max=9 ordinato ai fini dell'estrapolazione e infine l'elenco delle partizioni di
n=6 ricavato dal secondo elenco:
Codice:
1: 1 1 1 1 1 1 1 1 1
2: 2 1 1 1 1 1 1 1
3: 2 2 1 1 1 1 1
4: 2 2 2 1 1 1
5: 2 2 2 2 1
6: 3 1 1 1 1 1 1
7: 3 2 1 1 1 1
8: 3 2 2 1 1
9: 3 2 2 2
10: 3 3 1 1 1
11: 3 3 2 1
12: 3 3 3
13: 4 1 1 1 1 1
14: 4 2 1 1 1
15: 4 2 2 1
16: 4 3 1 1
17: 4 3 2
18: 4 4 1
19: 5 1 1 1 1
20: 5 2 1 1
21: 5 2 2
22: 5 3 1
23: 5 4
24: 6 1 1 1
25: 6 2 1
26: 6 3
27: 7 1 1
28: 7 2
29: 8 1
30: 9
1: 1 1 1 1 1 1 1 1 1
2: 2 1 1 1 1 1 1 1
3: 3 1 1 1 1 1 1
4: 2 2 1 1 1 1 1
5: 4 1 1 1 1 1
6: 3 2 1 1 1 1
7: 5 1 1 1 1
8: 2 2 2 1 1 1
9: 3 3 1 1 1
10: 4 2 1 1 1
11: 6 1 1 1
12: 3 2 2 1 1
13: 4 3 1 1
14: 5 2 1 1
15: 7 1 1
16: 2 2 2 2 1
17: 4 2 2 1
18: 3 3 2 1
19: 4 4 1
20: 5 3 1
21: 6 2 1
22: 8 1
23: 3 2 2 2
24: 3 3 3
25: 4 3 2
26: 5 2 2
27: 5 4
28: 6 3
29: 7 2
30: 9
1: 1 1 1 1 1 1 1
2: 2 1 1 1 1 1
3: 3 1 1 1 1
4: 2 2 1 1 1
5: 4 1 1 1
6: 3 2 1 1
7: 5 1 1
8: 2 2 2 1
9: 3 3 1
10: 4 2 1
11: 6 1
12: 3 2 2
13: 4 3
14: 5 2
15: 7
Infine credo di aver trovato anche un modo più efficiente rispetto a quello da te proposto per passare dalle partizioni di
n a quelle di
n+1, ma dimmi tu se ha ancora senso approfondire questa cosa alla luce di quanto scritto in questo post.
