IdentifiantMot de passe
Mot de passe oublié ?Je m'inscris ! (gratuit)
Voir le flux RSS

User

[Actualité] Mathématiques et Python : générer les partitions d'un entier

Note : 2 votes pour une moyenne de 3,00.
4 Commentaires
par
User
, 08/11/2023 à 13h59 (4997 Affichages)
I. Introduction

Après les partitions d'un ensemble, on s'intéresse maintenant aux partitions d'un entier :

L'objectif sera cette fois de créer une fonction itérative en Python qui pourra générer la liste des partitions d'un entier quelconque.

On va ensuite montrer comment transformer ce code en une fonction génératrice qui va nous permettre d'obtenir les partitions sans avoir besoin de les stocker dans une liste.



II. Partitions d'un entier


II-A. Définition mathématique

En mathématiques, une partition d'un entier (parfois aussi appelée partage d'un entier) est une décomposition de cet entier en une somme d'entiers strictement positifs (appelés parties ou sommants), à l'ordre près des termes (à la différence du problème de composition tenant compte de l'ordre des termes).

Une telle partition est en général représentée par la suite des termes de la somme, rangés par ordre décroissant.

Prenons par exemple le nombre entier 5, les 7 partitions de 5 sont :

  • 5 ;
  • 4 + 1 ;
  • 3 + 2 ;
  • 3 + 1 + 1 ;
  • 2 + 2 + 1 ;
  • 2 + 1 + 1 + 1 ;
  • 1 + 1 + 1 + 1 + 1.


Si on note 𝑝(n) le nombre de partitions de l'entier n, alors les premiers termes de la suite 𝑝(n) donnent :

𝑝(1) = 1, 𝑝(2) = 2, 𝑝(3) = 3, 𝑝(4) = 5, 𝑝(5) = 7, 𝑝(6) = 11, 𝑝(7) = 15, 𝑝(8) = 22, 𝑝(9) = 30, 𝑝(10) = 42, ...,
𝑝(50) = 204226, ..., 𝑝(100) = 190 569 292, ..., 𝑝(200) = 3 972 999 029 388, ...

On peut remarquer que la croissance de cette suite est très rapide.


II-B. Génération des partitions d'un entier

On va utiliser pour cela l'algorithme de construction décrit sur la page Wikipedia partition d'un entier :

La liste de toutes les partitions de 𝑛 dans l'ordre décroissant est donnée par un algorithme itératif.

Si une partition est représentée par une suite finie décroissante (𝑎𝑖) dont au moins un terme est strictement supérieur à 1, la partition suivante (𝑏𝑖) est construite comme suit :

On note 𝑘 le rang du dernier terme strictement supérieur à 1 et 𝑁 le nombre de termes qui valent 1 dans (𝑎𝑖).
Pour tout j < 𝑘, on définit 𝑏𝑗 = 𝑎𝑗.
On définit 𝑏𝑘 = 𝑎𝑘 − 1.
En notant 𝑁 + 1 = 𝑏𝑘𝑞 + 𝑟 la division euclidienne de 𝑁 + 1 par 𝑏𝑘, on définit les termes 𝑏𝑗 pour 𝑘 < 𝑗 < 𝑘 + 𝑞 + 1 par 𝑏𝑗 = 𝑏𝑘.
Si 𝑟 est non nul, on définit un dernier terme 𝑏𝑘+𝑞+1 = 𝑟.

On peut obtenir ainsi la liste des partitions pi de l'entier 5 :

Nom : tableau_algo.png Affichages : 4132 Taille : 30,0 Ko

L'objectif va être ensuite de traduire cet algorithme en Python.



III. Implémentation en Python


III-A. Génération de la liste des partitions d'un entier

On crée tout d'abord la fonction permettant de passer de la partition pi à la partition pi+1 :

Code Python : 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
def partition_suivante(a, k, N):
    # Construit la partition b qui suit la partition a dans la liste des partitions.
    # a : liste des entiers représentant la partition passée en argument
    # k : rang du dernier entier dans a strictement supérieur à 1
    # N : nombre d'entiers qui valent 1 dans la liste a 
 
    # pour tout j < k, on définit b[j] = a[j] : a = [2, 2, 1] -> b = [2]
    b = a[:k]
 
    # On ajoute (a[k] - 1) à la liste b : b[k] = a[k] - 1 : a = [2, 2, 1] -> b = [2, 1]
    b.append(a[k]-1)
 
    # En notant N+1 = b[k]*q + r la division euclidienne de N+1 par b[k] 
    # On obtient le quotient q et le reste r de cette division.
    q = (N+1) // b[k] ; r = (N+1) % b[k]
 
    # On évalue ensuite les entiers b[j] = b[k] pour k < j < k + q + 1 : a = [2, 2, 1] -> b = [2, 1] + 2*[1] = [2, 1, 1, 1]
    b = b + q*[b[k]]
 
    # Si le reste r est non nul.
    if r!=0: # ou : if r:
        # On ajoute l'entier r à la liste b : b[k+q+1] = r
        b.append(r)
 
    # calcul des valeurs de k et N pour la nouvelle partition b
    while (b[k]!=1):
        k+=1
        if k==len(b):
            break
 
    # renvoi de la partition b suivant la partition a, du rang k dans b, et du nombre N d'entiers valant 1 dans b
    return (b, k-1, len(b) - k)

Enfin, on crée la fonction principale permettant de générer la liste des partitions de l'entier n :

Code Python : 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
def generer_partitions(n):
    # Fonction principale permettant de générer la liste des partitions de l'entier n.
    # Partitions dont les termes sont rangés dans l'ordre décroissant : [[5], [4, 1], [3, 2], ..., [1, 1, 1, 1, 1,]]
 
    # 1re partition de la liste
    p = [n]
 
    # initialisation de la liste avec la 1re partition [n]
    partitions = [p]
 
    # initialisation des variables k et N
    # k : rang du dernier entier de [n] strictement supérieur à 1
    # N : nombre d'entiers qui valent 1 dans [n]
 
    # k=-1 et N=1 si n=1, sinon k=0 et N=0
    (k, N) = (-1, 1) if n==1 else (0, 0)
 
    # Tant que k est supérieur ou égal à 0 : si k=-1 on sort de la boucle
    while k>=0:
 
        # appel de la fonction renvoyant la partition suivant p, avec les paramètres k et N
        p, k, N = partition_suivante(p, k, N)
 
        # ajout de la nouvelle partition à la liste
        partitions.append(p)
 
    # renvoi de la liste des partitions : [5], [4,1], [3,2], ..., [1, 1, 1, 1, 1,]]
    return partitions

Testons maintenant la fonction :

Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
# Nombre entier dont on souhaite générer les partitions.
n = 5
 
# version n°1 : création de la liste des partitions de l'entier de départ
partitions = generer_partitions(n)
 
# Affiche les partitions une à une.
for partition in partitions:
    print(tuple(partition))

Le code affiche :

(5,)
(4, 1)
(3, 2)
(3, 1, 1)
(2, 2, 1)
(2, 1, 1, 1)
(1, 1, 1, 1, 1)



III-B. Fonction génératrice avec yield

Comme on l'a vu précédemment, le nombre de partitions croît très rapidement quand l'entier n augmente, ce qui risque d'entrainer des problèmes de mémoire insuffisante (MemoryError, ...).

On peut dans ce cas utiliser à la place une fonction génératrice qui va créer à la demande l'élément suivant de la séquence sans avoir besoin de le stocker dans une liste, permettant ainsi d’économiser de la mémoire.

Pour cela, Python dispose de l'instruction yield qui permet de transformer une fonction en générateur :

Code Python : 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
def generateur_partitions(n):
    # Fonction génératrice permettant de parcourir les partitions de l'entier n. 
    # Partitions dont les termes sont rangés dans l'ordre décroissant : [[5], [4, 1], [3, 2], ..., [1, 1, 1, 1, 1,]]
 
    # 1re partition de la liste
    p = [n]
 
    # renvoi de la 1re partition
    yield p
 
    # initialisation des variables k et N
    # k : rang du dernier entier de [n] strictement supérieur à 1
    # N : nombre d'entiers qui valent 1 dans [n]
 
    # k=-1 et N=1 si n=1, sinon k=0 et N=0
    (k, N) = (-1, 1) if n==1 else (0, 0)
 
    # Tant que k est supérieur ou égal à 0 : si k=-1 on sort de la boucle.
    while k>=0:
 
        # appel de la fonction renvoyant la partition qui suit p, avec les paramètres k et N
        p, k, N = partition_suivante(p, k, N)
 
        # renvoi de la nouvelle partition p
        yield p

Testons maintenant la fonction :

Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
# Nombre entier dont on souhaite générer les partitions.
n = 5
 
# version n°2 : création du générateur permettant de parcourir la liste des partitions de l'entier de départ
gen_partitions = generateur_partitions(n)
 
# Affiche les partitions une à une.
for partition in gen_partitions:
    print(tuple(partition))

Le code affiche :

(5,)
(4, 1)
(3, 2)
(3, 1, 1)
(2, 2, 1)
(2, 1, 1, 1)
(1, 1, 1, 1, 1)



III-C. Module complet

On donne enfin le code complet du module pour effectuer les tests :

Code Python : 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
def partition_suivante(a, k, N):
    # Construit la partition b qui suit la partition a dans la liste des partitions.
    # a : liste des entiers représentant la partition passée en argument
    # k : rang du dernier entier dans a strictement supérieur à 1
    # N : nombre d'entiers qui valent 1 dans la liste a 
 
    # pour tout j < k, on définit b[j] = a[j] : a = [2, 2, 1] -> b = [2]
    b = a[:k]
 
    # On ajoute (a[k] - 1) à la liste b : b[k] = a[k] - 1 : a = [2, 2, 1] -> b = [2, 1]
    b.append(a[k]-1)
 
    # En notant N+1 = b[k]*q + r la division euclidienne de N+1 par b[k] 
    # On obtient le quotient q et le reste r de cette division.
    q = (N+1) // b[k] ; r = (N+1) % b[k]
 
    # On évalue ensuite les entiers b[j] = b[k] pour k < j < k + q + 1 : a = [2, 2, 1] -> b = [2, 1] + 2*[1] = [2, 1, 1, 1]
    b = b + q*[b[k]]
 
    # Si le reste r est non nul.
    if r!=0: # ou : if r:
        # On ajoute l'entier r à la liste b : b[k+q+1] = r
        b.append(r)
 
    # calcul des valeurs de k et N pour la nouvelle partition b
    while (b[k]!=1):
        k+=1
        if k==len(b):
            break
 
    # renvoi de la partition b suivant la partition a, du rang k dans b, et du nombre N d'entiers valant 1 dans b
    return (b, k-1, len(b) - k)
 
 
def generer_partitions(n):
    # Fonction principale permettant de générer la liste des partitions de l'entier n.
    # Partitions dont les termes sont rangés dans l'ordre décroissant : [[5], [4, 1], [3, 2], ..., [1, 1, 1, 1, 1,]]
 
    # 1re partition de la liste
    p = [n]
 
    # initialisation de la liste avec la 1re partition [n]
    partitions = [p]
 
    # initialisation des variables k et N
    # k : rang du dernier entier de [n] strictement supérieur à 1
    # N : nombre d'entiers qui valent 1 dans [n]
 
    # k=-1 et N=1 si n=1, sinon k=0 et N=0
    (k, N) = (-1, 1) if n==1 else (0, 0)
 
    # Tant que k est supérieur ou égal à 0 : si k=-1 on sort de la boucle
    while k>=0:
 
        # appel de la fonction renvoyant la partition suivant p, avec les paramètres k et N
        p, k, N = partition_suivante(p, k, N)
 
        # ajout de la nouvelle partition à la liste
        partitions.append(p)
 
    # renvoi de la liste des partitions : [5], [4,1], [3,2], ..., [1, 1, 1, 1, 1,]]
    return partitions
 
 
def generateur_partitions(n):
    # Fonction génératrice permettant de parcourir les partitions de l'entier n. 
    # Partitions dont les termes sont rangés dans l'ordre décroissant : [[5], [4, 1], [3, 2], ..., [1, 1, 1, 1, 1,]]
 
    # 1re partition de la liste
    p = [n]
 
    # renvoi de la 1re partition
    yield p
 
    # initialisation des variables k et N
    # k : rang du dernier entier de [n] strictement supérieur à 1
    # N : nombre d'entiers qui valent 1 dans [n]
 
    # k=-1 et N=1 si n=1, sinon k=0 et N=0
    (k, N) = (-1, 1) if n==1 else (0, 0)
 
    # Tant que k est supérieur ou égal à 0 : si k=-1 on sort de la boucle.
    while k>=0:
 
        # appel de la fonction renvoyant la partition qui suit p, avec les paramètres k et N
        p, k, N = partition_suivante(p, k, N)
 
        # renvoi de la nouvelle partition p
        yield p
 
 
# Nombre entier dont on souhaite générer les partitions.
n = 5
 
# Affiche le nombre entier.
print("Partitions de " + str(n))
 
print()
 
print("Génération des partitions de l'entier..\n")
 
print("I. Version n°1 : méthode classique\n")
 
# version n°1 : génère la liste des partitions de l'entier n
partitions = generer_partitions(n)
 
print("Liste des partitions de n :\n")
 
# Affiche les partitions une à une.
for partition in partitions:
    print(tuple(partition))
 
print()
 
print("II. Version n°2 : fonction génératrice avec yield\n")
 
# version n°2 : crée le générateur permettant de parcourir la liste des partitions de l'entier de départ
gen_partitions = generateur_partitions(n)
 
print("Liste des partitions de n :\n")
 
# Affiche les partitions une à une.
for partition in gen_partitions:
    print(tuple(partition))


IV. Conclusion

Après avoir décrit l'algorithme permettant d'obtenir les partitions d'un entier, on a donc pu générer en Python la liste des partitions d'un entier quelconque.

Enfin, on a créé une fonction génératrice à partir de ce code, pour éviter les problèmes de mémoire insuffisante.


Sources :

https://fr.wikipedia.org/wiki/Partition_d%27un_entier
https://fr.wikiversity.org/wiki/Algo...it%C3%A9rative
https://gayerie.dev/docs/python/pyth...es-generateurs

Envoyer le billet « Mathématiques et Python : générer les partitions d'un entier » dans le blog Viadeo Envoyer le billet « Mathématiques et Python : générer les partitions d'un entier » dans le blog Twitter Envoyer le billet « Mathématiques et Python : générer les partitions d'un entier » dans le blog Google Envoyer le billet « Mathématiques et Python : générer les partitions d'un entier » dans le blog Facebook Envoyer le billet « Mathématiques et Python : générer les partitions d'un entier » dans le blog Digg Envoyer le billet « Mathématiques et Python : générer les partitions d'un entier » dans le blog Delicious Envoyer le billet « Mathématiques et Python : générer les partitions d'un entier » dans le blog MySpace Envoyer le billet « Mathématiques et Python : générer les partitions d'un entier » dans le blog Yahoo

Mis à jour 27/03/2024 à 06h15 par User

Catégories
Programmation , Python , Algorithmique

Commentaires

  1. Avatar de unanonyme
    • |
    • permalink
    Bonjour,

    Merci pour la ressource, intéressant ! Question annexe, ça sert à quel genre d'applications ces calculs ?

    Par curiosité j'ai porté votre bout de code en Go, on fait x2.
    C'est pas mal pour un portage sans douleur.

    Code Go : 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
    func partition_suivante(a []int, k, N int) ([]int, int, int) {
	// # Construit la partition b qui suit la partition a dans la liste des partitions.
	// # a : liste des entiers représentant la partition passée en argument
	// # k : rang du dernier entier dans a strictement supérieur à 1
	// # N : nombre d'entiers qui valent 1 dans la liste a
 
	b := make([]int, 0, k+3)
	b = append(b[:0], a[:k]...)
 
	// # pour tout j < k, on définit b[j] = a[j] : a = [2, 2, 1] -> b = [2]
	// b := a[:k]
 
	// # On ajoute (a[k] - 1) à la liste b : b[k] = a[k] - 1 : a = [2, 2, 1] -> b = [2, 1]
	b = append(b, a[k]-1)
 
	// # En notant N+1 = b[k]*q + r la division euclidienne de N+1 par b[k]
	// # On obtient le quotient q et le reste r de cette division.
	q := int(math. Floor(float64(N+1) / float64(b[k])))
	r := (N + 1) % b[k]
 
	// # On évalue ensuite les entiers b[j] = b[k] pour k < j < k + q + 1 : a = [2, 2, 1] -> b = [2, 1] + 2*[1] = [2, 1, 1, 1]
	for e := 0; e < q; e++ {
		b = append(b, b[k])
	}
 
	// # Si le reste r est non nul.
	if r != 0 {
		// # On ajoute l'entier r à la liste b : b[k+q+1] = r
		b = append(b, r)
	}
 
	// # calcul des valeurs de k et N pour la nouvelle partition b
	for b[k] != 1 {
		k++
		if k == len(b) {
			break
		}
	}
 
	// # renvoi de la partition b suivant la partition a, du rang k dans b, et du nombre N d'entiers valant 1 dans b
	return b, k - 1, len(b) - k
}


    Si on pousse l'optimisation un petit peu on fait encore 2x, mais si on est vraiment motivé je crois qu'on peut faire beaucoup mieux en généralisant cette ébauche.
    Ici, seul les 1 sont optimisés, on peut généraliser cela et gagner sur les durées d'allocations.

    Code Go : 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
    type partition struct {
	a    []int
	n    int
	ones int
}
 
func (p partition) is_last() bool {
	return len(p.a) < 1 || p.a[0] == 1
}
 
func (p partition) len() int {
	return len(p.a) + p.ones
}
 
func (p partition) slice() []int {
	out := make([]int, p.len())
	copy(out, p.a)
	for i := 0; i < p.ones; i++ {
		out[len(p.a)+i] = 1
	}
	return out
}
 
func partition_from_slice(s []int) partition {
 
	n := 0
	i := 0
	for ; i < len(s); i++ {
		if s[i] == 1 {
			break
		}
		n += s[i]
	}
	ones := len(s) - i
 
	return partition{
		a:    s[:i],
		n:    n + ones,
		ones: ones,
	}
}
 
func gen_part(p partition) partition {
 
	if p.is_last() {
		return p
	}
 
	n := p.a[len(p.a)-1]
 
	if n == 2 {
		np := partition{
			a:    make([]int, len(p.a)-1),
			n:    p.n,
			ones: p.ones + 2,
		}
		copy(np.a, p.a)
		return np
	}
 
	if len(p.a) == 1 {
		np := partition{
			a:    make([]int, 0, 10),
			n:    p.n,
			ones: 0,
		}
		j := 0
		m := n - 1
		for {
			if j+m > np.n {
				break
			}
			np.a = append(np.a, m)
			j += m
		}
		if u := np.n - j; u > 1 {
			np.a = append(np.a, u)
		} else if u > 0 {
			np.ones++
		}
		return np
	}
 
	if p.ones < 1 {
		np := partition{
			a:    make([]int, len(p.a)),
			n:    p.n,
			ones: 1,
		}
		copy(np.a, p.a)
		np.a[len(p.a)-1]--
		return np
	}
 
	np := partition{
		a:    make([]int, len(p.a)+1),
		n:    p.n,
		ones: 0,
	}
	copy(np.a, p.a)
	n--
	ones := p.ones + 1
	np.a[len(p.a)-1] = n
	if n > ones {
		np.a[len(p.a)] = ones
	} else {
		np.a[len(p.a)] = n
		o := 0
		for _, j := range np.a {
			o += j
		}
		for o < p.n {
			r := p.n - o
			if r >= n {
				np.a = append(np.a, n)
			} else if r > 1 {
				np.a = append(np.a, r)
			} else {
				np.ones++
				break
			}
			o += n
		}
	}
	return np
}

    Quelques cas de tests pour montrer l'utilisation.

    Code Go : 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
    package main
 
import (
	"fmt"
	"reflect"
	"testing"
)
 
func TestGenPart(t *testing.T) {
 
	type tcase struct {
		input      []int
		expect     []int
		expect_end bool
	}
 
	cases := []tcase{
		{
			input:  []int{15},
			expect: []int{14, 1},
		},
		{
			input:  []int{10, 5},
			expect: []int{10, 4, 1},
		},
		{
			input:  []int{7, 1, 1, 1, 1, 1, 1, 1, 1},
			expect: []int{6, 6, 3},
		},
		{
			input:  []int{4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			expect: []int{3, 3, 3, 3, 3},
		},
		{
			input:  []int{6, 6, 3},
			expect: []int{6, 6, 2, 1},
		},
		{
			input:      []int{1},
			expect:     []int{1},
			expect_end: true,
		},
		{
			input:      []int{1, 1, 1},
			expect:     []int{1, 1, 1},
			expect_end: true,
		},
		{
			input:      []int{2, 1, 1},
			expect:     []int{1, 1, 1, 1},
			expect_end: true,
		},
		{
			input:      []int{2, 1, 1, 1, 1, 1, 1},
			expect:     []int{1, 1, 1, 1, 1, 1, 1, 1},
			expect_end: true,
		},
		{
			input:  []int{3, 3, 3, 3, 3},
			expect: []int{3, 3, 3, 3, 2, 1},
		},
		{
			input:  []int{3, 2, 1},
			expect: []int{3, 1, 1, 1},
		},
		{
			input:  []int{4, 4},
			expect: []int{4, 3, 1},
		},
		{
			input:  []int{5, 3},
			expect: []int{5, 2, 1},
		},
		{
			input:  []int{18, 2},
			expect: []int{18, 1, 1},
		},
		{
			input:  []int{18, 1, 1},
			expect: []int{17, 3},
		},
		{
			input:  []int{6, 6, 6, 1, 1},
			expect: []int{6, 6, 5, 3},
		},
		{
			input:  []int{14, 3, 1, 1, 1},
			expect: []int{14, 2, 2, 2},
		},
		{
			input:  []int{15, 3, 1, 1},
			expect: []int{15, 2, 2, 1},
		},
		{
			input:  []int{12, 4, 1, 1, 1, 1},
			expect: []int{12, 3, 3, 2},
		},
	}
 
	for i, c := range cases {
		p := partition_from_slice(c.input)
		res := gen_part(p)
 
		if !reflect.DeepEqual(res.slice(), c.expect) {
			fmt.Printf("%#v\n", p)
			fmt.Printf("%#v\n", res)
			t.Fatalf(`invalid result at #%v
		expected    %#v
		result      %#v`, i, c.expect, res.slice())
		}
		if c.expect_end != res.is_last() {
			t.Fatalf(`invalid result at #%v
		expected    %#v
		result      %#v`, i, c.expect_end, res.is_last())
		}
	}
}

    Évidemment, si on pouvait trouver à répartir les de calculs sur plusieurs fils d'exécution on gagnerait d'autant plus, mais la répartition de la charge n'est pas évidente.

    Bref, des babioles sans conséquence.

    Bonne journée.
    Mis à jour 12/11/2023 à 12h47 par f-leb (balises [CODE=Go]...[/CODE] pour coloration syntaxique)
  2. Avatar de User
    • |
    • permalink
    Bonjour et merci pour votre message,

    Tout ce qu'on apprend en maths ou dans d'autres matières n'a pas toujours une application directe, mais déjà avoir la satisfaction de comprendre les choses, en rendant accessible un sujet pas forcément simple de prime abord ça peut être sympa..

    Concernant le code, l'objectif était surtout d'écrire du code le plus lisible possible, sans chercher forcément la performance, car le billet ne s'adresse pas à des experts en programmation En tout cas chercher le meilleur compromis entre les deux.

    Je voulais aussi proposer quelque chose de différent de ce qu'on trouve habituellement sur les forums, autre chose par exemple que les fonctions récursives..

    En tout cas merci pour le code, je ne connais pas Go

    Cordialement,
  3. Avatar de unanonyme
    • |
    • permalink
    Bonjour,

    Merci pour votre réponse.

    Expert, je ne sais pas, curieux, volontiers.

    Oui la lisibilité en a pris un coup pour supprimer les divisions et modulos.
    Le manque de commentaire n'y aide pas et la relecture me fait penser
    que ce n'est pas une implémentation optimale.

    Mais il n'y a vraiment rien de spécial la dedans, la série produite présente
    des cas particuliers pour faire pivoter les valeurs.
    L'algo s'appuie la dessus. (4, 1) (3, 1, 1) (2, 1, 1, 1) etc

    Bonne journée.
  4. Avatar de User
    • |
    • permalink
    Bonjour,

    Oui la bonne curiosité merci pour ces précisions.

    En fait concernant l'optimisation l'objectif était surtout ensuite d'économiser de la mémoire (2nde version).

    Cdlt,