Discussion :

[gorgonite]

tout a l'air de bien fonctionner

les performances (g++ avec option -O2)
+ n=21 => 4 ms
+ n=54 => 92 ms
+ n=70 => 1 s
+ n=100 => 48s





pour infos, nous allons faire un récapitulatif avec les codes et les perfs...
temporairement, ce post de benchmarks peut vous donner une idée...

[millie]

Ok, ma version a en fait toujours été buggué... Mon idée de départ était fausse



J'ai corrigé, mais les performances tombent un peu... Faut que je parte à la recherche d'une nouvelle idée.


Snif snif, les langages fonctionnels reprennent la tête

Code C++ :

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
#include <iostream>
#include <vector>
 
/*affiche un vecteur*/
void afficher(std::vector<int> & list)
{
    std::cout<<"[";
    for(int i =0; i <list.size()-1; i++)
        std::cout<<list[i]<<", ";
    std::cout<<list[list.size()-1];
 
    std::cout<<"], "<<std::endl;
}
 
/*calcul la somme d'un vecteur*/
int somme(std::vector<int> & list)
{
    int total = 0;
    for(int i=0; i<list.size(); i++)
        total += list[i];
    return total;
}
 
/*met tout le vecteur à 1 sauf le premier élément à n*/
void mettrePremierN(std::vector<int> & list, int n)
{
    list[0] = n;
    for(int i = 1; i<list.size(); i++)
        list[i] = 1;
}
 
/*genère la combinaison suivante suivant un critère très particulier*/
void genererSuivant(std::vector<int> & list)
{
    int currentMax = 0;
    int pos = 0;
 
    for(pos=0; pos<list.size()-1; pos++)
        if(list[pos+1]< list[pos])
            currentMax = pos+1;
 
    if(pos == list.size()-1) {
        list[currentMax]++;
        for(pos=currentMax+1; pos<list.size(); pos++)
            list[pos] = 1;
    }
}
 
/*génère l'ensemble des solutions dont la taille du vecteur vaut taille*/
void generationSolution(int n, int taille)
{
    static std::vector<int> list;
    list.resize(taille);
    for(int i=0; i<taille; i++)
        list[i] = 1;
 
    for(int i=n/taille; i<=n+1-taille; i++)
    {
        int total = 0;
        mettrePremierN(list, i); //somme vaut i>=n+1-taille
                                    //dans la boucle, ça sera au maximum = taille * i
        while(list[0]==i)
        {
            total = somme(list);
          // if(total == n)
           //     afficher(list);
           // if(total >=n)
            //    break;
            genererSuivant(list);
        }
    }
 
}
 
/*génère l'ensemble des solutions*/
void generationSomme(int n)
{
    for(int taille = n; taille>0; taille--)
        generationSolution(n, taille);
}
 
int main()
{
/*    std::vector<int> list;
    list.push_back(4);
    list.push_back(1);
    list.push_back(1);
 
    for(int i=0; i<4; i++) {
     genererSuivant(list);
     afficher(list);
    }*/
 
    generationSomme(100);
 
    return 0;
}

[strate]

Mais pourquoi personne n'aime mon code :'(

Parce que tu n'as pas expliqué ce qu'il fait ni comment il marche. Ca pourrait être le code le plus génial du monde, s'il laisse l'impression qu'il ne répond pas à la question et que tu ne fais rien pour nous aider à comprendre, il aura peu de succès... Les perfs annoncées sont brillantes et un peu incroyables, à toi de nous faire passer le message.

Je ne suis pas juste pénible par plaisir, c'est une question fondamentale quand on développe du code : faire en sorte que ceux qui l'utilisent aient confiance.

[Jean-Marc.Bourguet]

Parce que tu n'as pas expliqué ce qu'il fait ni comment il marche.

Il construit un DAG dont les chemins de la racine aux feuilles sont les solutions. Les autres propositions generent toutes les solutions (soit en les conservant, soit en ne le faisant pas), ce qui est different.

Si on ajoute le parcours des chemins, sa solution n'est pas tellement (ou meme pas du tout?) meilleure. En fait on peut meme dire que les autres solutions parcourent aussi le meme DAG sans prendre la peine de le construire.


Autre proposition en C++ -- qui itere toujours sur toutes les solutions --, en utilisant une representation qui comprime les 1 finaux. On peut pousser cette idee plus loin en utilisant du RLE pour tous les elements ou une representation des comptes (donc avec beaucoup de 0, ca ne va vraissemblablement pas apporter grand chose).

Code c++ :

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
 
void consume(std::vector<long> const& tab, int trailing1s) {
#ifdef COUNT_ONLY
  ++solutions;
#else
  if (!tab.empty()) {
      std::cout << tab[0];
      for (std::vector<long>::size_type i = 1; i < tab.size(); ++i)
      {
          std::cout << ", " << tab[i];
      }  
  } else {
      std::cout << '1';
      --trailing1s;
  }
  while (trailing1s != 0) {
      std::cout << ", 1";
      --trailing1s;
  }
  std::cout << '\n';
#endif
}
 
void generate(long val)
{
    std::vector<long> result;
    result.reserve(val);
    result.push_back(val);
    long remainder = 0;
    consume(result, remainder);
    while (!result.empty()) {
        long last = result.back();
        result.pop_back();
        remainder += last;
        --last;
        if (last != 1) {
            while (remainder >= last) {
                result.push_back(last);
                remainder -= last;
            }
            if (remainder > 1) {
                result.push_back(remainder);
                remainder = 0;
            }
        }
        consume(result, remainder);
    }
}

[Trap D]

temporairement, ce post peut vous donner une idée... http://www.developpez.net/forums/sho...4&postcount=29

Tu aurais du corriger pour le code C, après vérification, il me semble qu'il arrive assez bien placé (version 2 avec optimisation de vitesse)

pour 50 : 0.016 s
pour 70 : 0.250 s
pour 80 : 1.016 s
pour 90 : 3.781 s
pour 100 : 13.104 s

PS : J'ai ajouté le programme C, c'est du windows à cause de GetTickCount().

[Trap D]

Et pour n = 100, il retourne 122072 solution alors qu'il y en a 2300165032574323995027.

Non, pour n = 100, le nombre de décomposition est 190 569 292
voir ici

[Jedai]

Je rajoute une implémentation en Haskell, elle n'est pas destinée à être rapide (ce qu'elle n'est pas vraiment, enfin elle doit être au niveau des codes OCaml de Gorgonite à peu près), mais elle est belle (de mon point de vue ) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import System

combinations = foldl (\without p ->
                          let (poor,rich) = splitAt p without
                              with = poor ++ 
                                     zipWith (++) (map (map (p:)) with)
                                                  rich
                          in with
                     ) ([[]] : repeat [])

main = do
  args <- getArgs
  let n = read $ args !! 0
  print . length $ combinations [1..n] !! n

Néanmoins elle emploie à plein l'évaluation paresseuse et fait usage d'une valeur récursive et infinie pour faire de la programmation dynamique !

De plus sa portée est plus générale que la plupart des programmes présents ici car elle permet d'entrer une liste d'entiers utilisables, elle résout de façon très élégante et très efficace le problème du menu (que pouvez vous vous acheter à la carte pour une somme donnée ?) (plus connu sous le nom de knapsack).

(Malheureusement la solution n'est pas de moi, je reproduis de mémoire une fonction dont j'ai vu la définition sur une mailing-list en réponse à ce webcomic (très fun pour les informaticiens par ailleurs))

--
Jedaï

[Jedai]

Je rappelle que ce post fournit une comparaison de la plupart des programmes présentés dans ce sujet.
Les tests ont été fait sous Windows XP, un pentium M 1.73Mhz, 1Go de RAM (dont 400Mo occupés).

--
Jedaï

[HanLee]

(Malheureusement la solution n'est pas de moi, je reproduis de mémoire une fonction dont j'ai vu la définition sur une mailing-list en réponse à ce webcomic (très fun pour les informaticiens par ailleurs))

--
Jedaï

(je sais, j'ai pas de proposition sous la main... J'vais peut-être en donner plus tard)

[Steki-kun]

Coucou tout le monde, je savais pas quoi faire cette apres-midi alors j'ai essayé de faire la mienne. En OCaml (très impur mais mon but n'était pas de le faire pur ) avec tableaux : je fais que parcourir toutes les solutions sans les garder en mémoire. Elles sont calculées dans l'ordre lexicographique inverse selon l'algo donné dans TAOCP.

Pour l'appeler : ./partP -n 64, ajouter -debug pour voir toutes les solutions et leur nombre, et si vous rediriger vers /dev/null il vous donnera quand même le nombre de solutions sur la sortie err.

Compilé avec ocamlopt -unsafe (mais le -unsafe m'a quasimment rien fait gagner) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
...@...:.../Partitions$ time ./partP -n 32
real	0m0.005s user	0m0.000s sys	0m0.000s

...@...:.../Partitions$ time ./partP -n 64
real	0m0.065s user	0m0.056s sys	0m0.004s

...@...:.../Partitions$ time ./partP -n 100
real	0m2.610s user	0m2.608s sys	0m0.000s

Je sais que time c'est pas la panacée pour faire des benchs mais j'en ai fait plusieurs et j'ai pris un "moyen", ça donne une idée.

Le code OCaml :

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
let debug = ref false
let sol = ref 0

let visit a m = 
  incr sol;
  for i = 1 to m-1 do
    Printf.printf "%d+" a.(i)
  done;
  print_endline (string_of_int a.(m))

let rec copy_loop a n m x =
  if n <= x then n, m
  else 
    (a.(m) <- x;
     copy_loop a (n-x) (m+1) x)

let rec main_loop a n m q =
  if !debug then visit a m;
  if a.(q) = 2 then
    (a.(q) <- 1;
     a.(m+1) <- 1;
     main_loop a n (m+1) (q-1))
  else
    if q = 0 then ()
    else
      begin
	let x = a.(q) - 1 in 
	  a.(q) <- x;
	  let n,m = copy_loop a (m-q+1) (q+1) x in
	    a.(m) <- n;
	    main_loop a n m (m - (if n=1 then 1 else 0))
      end

      
let main n =
  if n < 1 then raise (Invalid_argument "n should be positive");
  let a = Array.make (n+1) 0 in
    a.(1) <- n;
    main_loop a n 1 (if n = 1 then 0 else 1)

let usage = 
  Printf.sprintf 
    "%s <n> <t>\n  Generates all partitions of n\n"
    (Sys.argv.(0))

let n = ref 0
let _ = 
  Arg.parse [("-debug", Arg.Set debug, "prints each partition");
	     ("-n", Arg.Set_int n, "integer to partition")]
    (fun s -> print_endline usage)
    usage;
  main !n;
  if !debug then 
    Printf.eprintf "Number of solutions visited : %d\n" !sol

[yan]

Bonjour,
en regardant le code millie
http://www.developpez.net/forums/sho...0&postcount=55
j'ai vue qu'il y avait encore une optimisation a faire. Et pour tester je l'ai refait en utilisant la STL.
Grosse déception, c'est moins rapide sous GCC même sans rajouter l'optimisation :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
void genererSuivant(std::vector<int> & list)
{
//diminue le nombre de test 
  for(pos=list.size()-2;pos>= 0 && list[pos+1]>= list[pos]; pos--);

    if(list[pos+1]< list[pos])
        list[pos+1]++;
    else
         list[0]++;
}

le voila avec la STL

Code C++ :

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
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <numeric>
#include <ctime>
 
 
/*affiche un vecteur*/
void afficherMongaulois(const std::vector<int> & list)
{
    std::cout<<"[";
    std::copy(list.begin(),list.end()-1,std::ostream_iterator<int>(std::cout,", "));
    std::cout<< *list.rbegin()<<"]\n ";
}
 
/*calcul la somme d'un vecteur*/
int sommeMongaulois(const std::vector<int> & list)
{
    return std::accumulate(list.begin(),list.end(),0);
}
 
/*met tout le vecteur à 1 sauf le premier élément à n*/
void mettrePremierNMongaulois(std::vector<int> & list,const int &n)
{
    list[0] = n;
    std::fill(list.begin()+1,list.end(),1);
}
 
/*genère la combinaison suivante suivant un critère très particulier*/
void genererSuivantMongaulois(std::vector<int> & list)
    {
     std::vector<int>::reverse_iterator it = std::adjacent_find( list.rbegin(), list.rend(),std::less<int>());
 
    if(list.rend()!=it)
        (*it)++;
    else
        (*list.begin())++;
    }
 
/*génère l'ensemble des solutions dont la taille du vecteur vaut taille*/
void generationSolutionMongaulois(int n, int taille)
{
    static std::vector<int> list;
    list.resize(taille);
    std::fill(list.begin(),list.end(),1);
 
 
    for(int i=n/taille; i<=n+1-taille; i++)
    {
        int total = 0;
        mettrePremierNMongaulois(list, i); //somme vaut i>=n+1-taille
                                    //dans la boucle, ça sera au maximum = taille * i
        while(total<=n && list[0]==i)
        {
            total = sommeMongaulois(list);
            if(total == n)
                afficherMongaulois(list);
            if(total >=n)
                break;
            genererSuivantMongaulois(list);
        }
    }
 
}
 
/*génère l'ensemble des solutions*/
void generationSommeMongaulois(int n)
{
    for(int taille = n; taille>0; taille--)
        generationSolutionMongaulois(n, taille);
}
 
int main(int argc,char ** argv)
{
    int nb = 100;
 
    generationSommeMongaulois(nb);
    return 0;
}

Es ce que quelqu'un pourrai tester pour vérifier les résultat?
merci

[millie]

En fait, mon code est faux, il me manque des parties

En tout cas, ce qui est sûr, c'est que ma solution où j'étais partie sera peut être au final plus rapide, mais j'ai passé un maximum de temps à résoudre le problème en amont alors que les solutions de bases fonctionnels laissent tout le travail au programme.
Mais il doit y avoir des versions fonctionnels plus réfléchies, faudrait que je relise les quelques pages.

[Steki-kun]

Euh, la mienne est très réfléchie ! Je peux la réécrire en fonctionnel pur et elle reste tout à fait réfléchie : en remplaçant le tableau de taille constante sur lequel l'algo travaille par une liste de couples (n,k) représentant de manière condensée la partition où k est présent n fois, et en les générant à l'envers pour profiter d'un meilleur sharing (les petits facteurs de la partition changent souvent sans que les gros ne changent). C'est forcément plus lent que l'autre à cause des allocations et des copies en plus, mais ça reste efficace.

...:~/.../Partitions$ time ./partPpur -n 32
user 0m0.000s

...:~/.../Partitions$ time ./partPpur -n 64
user 0m0.108s

...:~/.../Partitions$ time ./partPpur -n 100
user 0m5.236s

Voilà le code, la boucle principale en gras :

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
open Int64

let debug = ref false
let sol = ref zero

let rec visit = function
    [] -> assert false
  | [(ck,ak)] -> 
      sol := add !sol one;
      let sk = string_of_int ak in
      let skp = sk^"+" in
	for i = 1 to (ck-1) do 
	  print_string skp;
	done; print_endline sk
  | (ck,ak)::q -> 
      let sk = string_of_int ak in
      let skp = sk^"+" in
	for i = 1 to ck do 
	  print_string skp;
	done; visit q

let rec main_loop n l =
  if !debug then visit (List.rev l);
  match l with
    | [] -> assert false
    | [(_,1)] -> ()
    | (ck,1)::(dk, 2)::q -> 
	let q' = if dk=1 then q else (dk-1,2)::q in
	  main_loop n ((ck+2,1)::q')
    | (ck,1)::(dk, ak)::q -> 
	let x = ak-1 in
	let q' = if dk=1 then q else (dk-1,ak)::q in
	let quot = (ck+1)/x in
	let r = (ck+1)-x*quot in
	  main_loop n 
	    (if r = 0 then
	       (quot+1,x)::q'
	     else
	       (1,r)::(quot+1,x)::q')	    
    | (dk,2)::q ->
	let q' = if dk=1 then q else (dk-1,2)::q in
	  main_loop n ((2,1)::q')
    | (dk,ak)::q ->
	let q' = if dk=1 then q else (dk-1,ak)::q in
	  main_loop n ((1,1)::(1,ak-1)::q')
      
let main n =
  if n < 1 then raise (Invalid_argument "n should be positive");
  main_loop n [(1,n)]

let usage = 
  Printf.sprintf 
    "%s <n> <t>\n  Generates all partitions of n\n"
    (Sys.argv.(0))

let n = ref 0
let _ = 
  Arg.parse [("-debug", Arg.Set debug, "prints each partition");
	     ("-n", Arg.Set_int n, "integer to partition")]
    (fun s -> print_endline usage)
    usage;
  main !n;
  if !debug then Printf.eprintf "Number of solutions visited : %s\n" (to_string !sol)

Il y a de la duplication dans le matching, c'est pour traiter efficacement le cas simple et très fréquent où la partition est de la forme n = .. + ... + 2 + 1 + 1 + 1 ... + 1.

[yan]

En fait, mon code est faux, il me manque des parties

En tout cas, ce qui est sûr, c'est que ma solution où j'étais partie sera peut être au final plus rapide, mais j'ai passé un maximum de temps à résoudre le problème en amont alors que les solutions de bases fonctionnels laissent tout le travail au programme.
Mais il doit y avoir des versions fonctionnels plus réfléchies, faudrait que je relise les quelques pages.

ha ok.
J'ai pas du voir où c'était ecrit...
Ben tans pis (c'était surtout pour voir comment le réécrire avec la STL et verifier que c'etait plus, ou au moins aussi, rapide... ).
Il y as juste les versions fonctionnelle qui sont correcte?

[millie]

Euh, la mienne est très réfléchie ! Je peux la réécrire en fonctionnel pur et elle reste tout à fait réfléchie : en remplaçant le tableau de taille constante sur lequel l'algo travaille par une liste de couples (n,k) représentant de manière condensée la partition où k est présent n fois, et en les générant à l'envers pour profiter d'un meilleur sharing (les petits facteurs de la partition changent souvent sans que les gros ne changent). C'est forcément plus lent que l'autre à cause des allocations et des copies en plus, mais ça reste efficace.


Voilà le code, la boucle principale en gras :

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
open Int64

let debug = ref false
let sol = ref zero

let rec visit = function
    [] -> assert false
  | [(ck,ak)] -> 
      sol := add !sol one;
      let sk = string_of_int ak in
      let skp = sk^"+" in
	for i = 1 to (ck-1) do 
	  print_string skp;
	done; print_endline sk
  | (ck,ak)::q -> 
      let sk = string_of_int ak in
      let skp = sk^"+" in
	for i = 1 to ck do 
	  print_string skp;
	done; visit q

let rec main_loop n l =
  if !debug then visit (List.rev l);
  match l with
    | [] -> assert false
    | [(_,1)] -> ()
    | (ck,1)::(dk, 2)::q -> 
	let q' = if dk=1 then q else (dk-1,2)::q in
	  main_loop n ((ck+2,1)::q')
    | (ck,1)::(dk, ak)::q -> 
	let x = ak-1 in
	let q' = if dk=1 then q else (dk-1,ak)::q in
	let quot = (ck+1)/x in
	let r = (ck+1)-x*quot in
	  main_loop n 
	    (if r = 0 then
	       (quot+1,x)::q'
	     else
	       (1,r)::(quot+1,x)::q')	    
    | (dk,2)::q ->
	let q' = if dk=1 then q else (dk-1,2)::q in
	  main_loop n ((2,1)::q')
    | (dk,ak)::q ->
	let q' = if dk=1 then q else (dk-1,ak)::q in
	  main_loop n ((1,1)::(1,ak-1)::q')
      
let main n =
  if n < 1 then raise (Invalid_argument "n should be positive");
  main_loop n [(1,n)]

let usage = 
  Printf.sprintf 
    "%s <n> <t>\n  Generates all partitions of n\n"
    (Sys.argv.(0))

let n = ref 0
let _ = 
  Arg.parse [("-debug", Arg.Set debug, "prints each partition");
	     ("-n", Arg.Set_int n, "integer to partition")]
    (fun s -> print_endline usage)
    usage;
  main !n;
  if !debug then Printf.eprintf "Number of solutions visited : %s\n" (to_string !sol)

Il y a de la duplication dans le matching, c'est pour traiter efficacement le cas simple et très fréquent où la partition est de la forme n = .. + ... + 2 + 1 + 1 + 1 ... + 1.

Je parlais surtout des premières réponses, mais je n'avais pas tout revu quand j'ai reposté ici, ça fait quelques temps qu'il n'y avait plus de réponse ici

[yan]

Bon ben,
vu que j'avais recodé un algo faux, j'ai fait ma propre solution en récursive avec C++

Code C++ :

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
#include <iterator>
 
//#define AFFICHER
int nbvalue(0);
 
inline void afficher(std::vector<int> & myVect,int nb)
{
    nbvalue++;
    #ifdef AFFICHER
    std::cout<<"[";
    std::copy(myVect.begin(),myVect.begin()+nb-1,std::ostream_iterator<int>(std::cout,", "));
    std::cout<<myVect[nb-1]<<"]\n";
    #endif
}
 
//fonction récussive
void generate(std::vector<int> & myVect,int & reste ,const  int & nb_precedent,int & level)
{
//si reste ==0 alors la somme des chiffres est bien ègale au chiffre de dépard
if (reste==0) afficher(myVect,level);
//on interdit que le chiffre que l'on va traiter puisse etre plus grand que le précédent
for (int i=(reste>nb_precedent) ? nb_precedent:reste;i>0 ;--i)
    {
    myVect[level] = i;
    int nextReste = reste-i;
    int nextLevel =level+1;
    //on traite le prochain chiffre avec le reste
    generate(myVect,nextReste,i,nextLevel);
 
    }
}
 
int main()
{
    clock_t t1=std::clock();
    int n =100;
    std::vector<int> myVect(n);
    int level =0;
    generate(myVect,n,n,level);
    clock_t t2=std::clock();
    std::cout<<nbvalue<<std::endl;
    std::cout<<double(t2-t1)/CLOCKS_PER_SEC<<std::endl;
    return 0;
}

mais je suis un peu plus lent que celui de Jean-Marc.Bourguet j'ai pas compris sont code...

[yan]

Pour les version fonctionnelles qui font de super score, il créé un arbre dont les solutions sont tous les trajet/graph entre la base et les feuilles. C'est bien cela?
Malheureusement leur score correspond uniquement à la création de cette arbre, non?
Si c'est bien cela, ne devrait il pas ajouter les parcours pour que l'on puisse réellement comparer les différent résultats?

[Steki-kun]

Si tu parles de la version d'alex pi, oui, et il y a je sais pas combien de posts où il est question de cela au cours de cette discussion

Les miennes visitent toutes les solutions en revanche, et leur fonctionnement est à peu près le même que celui de JMB, à savoir :
* on part de la décomposition triviale n = n
* on prend le premier terme à droite k qui soit > 1 dans la décomposition (s'il n'y en a pas, on a terminé)
* on le remplace par (k-1) + ... + (k-1) + r où (k-1) est présent q fois et où q(k-1)+r est la division euclidienne de (k+tous les 1 qui sont à droite) par (k-1), on a donc une nouvelle décomposition qui est la plus grande possible, tout en étant plus petite que la précédente (dans l'ordre lexicographique)
* on retourne à l'étape 2

Cet algo permet de visiter toutes les décompositions où les entiers sont rangés dans l'ordre décroissant, de n à 1 + 1 + .... + 1, dans l'ordre inverse de l'ordre lexicographique donc.

Dans sa 2ème version, JMB optimise en ne stockant pas les 1, il stocke juste le nombre de 1 dans remainder. Dans ma deuxième version, je généralise cette idée pour tous les entiers de la décomposition (pour minimiser la taille de mes listes). Et dans mes 2 versions, je traite spécialement le cas où k = 2 puisqu'il est fréquent et simple (idée donnée par Knuth dans le Volume 4 Fascicule 3 du Art of Computer Programming, by the way). Voilou

[yan]

ok, merci, je vais essayer de comprendre

Par contre j'ai n'ai pas trop compris le temps de tes résultats...
pour 100 tu arrive à 5.236s ??!!!!
tu as comparrai par rapport au code C++ sur t'as machine?
Sinon c'est marrant, mon code donne le même ordre de résultat que celui de JMB mais il ne fait pas la même chose

[Steki-kun]

J'arrive même a 2.6s sur la version impérative qui travaille à espace mémoire constant ; et non je n'ai pas compilé la version C++ chez moi, de tte façon j'ai pas un Cray chez moi c'est un AMD64 assez standard (et je n'utilise qu'un core) Il faut bien voir que quand n=100, il y a presque 80% des 191millions de partitions qui sont de la forme .... + 2 + 1 + 1 ... + 1 donc traiter ce cas là 'en place' au lieu de faire une boucle qui va remplacer les 1 par des 1 ça peut faire gagner beaucoup. Et la proportion va en augmentant quand n augmente.