Algorithme pour partitions d'un entier

Gilles old · February 2019

Bonjour,

J'ai trouvé sur cette page un algorithme pour calculer les partitions d'un entier $n$, mais je ne comprends pas son fonctionnement, ce n'est pourtant pas faute de l'avoir suivi pas-à-pas en rajoutant des "print" partout. Quelqu'un aurait-il le courage de m'expliquer ?

Merci d'avance.

def rule_asc(n):
    L=[]
    a = [0 for i in range(n)]
    k = 1
    a[1] = n
    while k != 0:
        x = a[k - 1] + 1
        y = a[k] - 1
        k -= 1
        while x <= y:
            a[k] = x
            y -= x
            k += 1
        a[k] = x + y
        L+=[a[:k + 1]]
    return L

>>> rule_asc(5)
[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 4], [2, 3], [5]]

Gilles old · February 2019

En continuant à fouiner sur ce sujet, je suis tombé sur la thèse de l'auteur dans lequel il donne la démonstration de cet algorithme. Je vais étudier cela, désolé du dérangement. :-D

Rescassol · February 2019

Bonsoir
Pourrais-tu donner le lien vers cette thèse ?
Cordialement,
Rescassol

Poirot · February 2019

Elle est dans le dernier message de Gilles, ne vois-tu pas le mot "thèse" en vert, indiquant un lien ?

claude quitté · February 2019

@Gilles
Je n'ai pas regardé la thèse de l'auteur. Lorsque l'on examine l'algorithme que tu as donné, on s'aperçoit qu'il calcule le successeur d'une partition, successeur au sens de l'ordre lexicographique. Personnellement, avant de montrer un truc fini efficace, je préfère montrer quelque chose qui me semble plus clair. Et qui fait exactement la même chose que l'algorithme donné

[color=#000000]
Successeur := function(a)
  // a est une partition de n (croissante au sens large)
  // Retourne la partition b de n, successeur de a dans l'ordre lexicographique
  // Exception : si la longeur k de a est 1 i.e. a = [n], retourne a.
  assert Sort(a) eq a ;
  k := #a ;
  if k eq 1 then return a ; end if ;
  // Utilisation les deux derniers éléments de a pour fabriquer la partition successeur b
  y := a[k] - 1 ;
  x := a[k-1] + 1 ;
  q := Quotrem(y,x)  ; // q quotient de y par x
  // b = a[1..k-2] \/  [x,x, .., x (q fois)] \/ [y-q*x] de longueur k-2 + q + 1 = k-1+q
  // Alors b est croissante de somme n (= somme de a)
  b := a[1..k-2] cat [x^^q] cat [y-(q-1)*x] ;
  assert #b eq k+q-1  and   &+a eq &+b   and  Sort(b) eq b ;
  return b ;
end function ;
[/color]

Je ne détaille pas plus i.e. je ne donne pas de véritable explication.
Je vais l'utiliser ainsi (bien entendu je suis susceptible d'élaborer une fonction qui fait le job en fonction de $n$)

[color=#000000]
n := 5 ;
a := [1^^n] ;
a ;
L := [a] ;
// Volontairement pas efficace car je sollicite 2 fois Successeur
// [[mais en un premier temps, je préfère procéder ainsi]]
repeat a := Successeur(a) ; Append(~L, a) ; until Successeur(a) eq a ;
L ;
[/color]

Ce qui va donner cela

[color=#000000]
> n := 5 ;
> a := [1^^n] ;
> a ;
[ 1, 1, 1, 1, 1 ]
> L := [a] ;
> repeat a := Successeur(a) ; Append(~L, a) ; until Successeur(a) eq a ;
> L ;
[
    [ 1, 1, 1, 1, 1 ],
    [ 1, 1, 1, 2 ],
    [ 1, 1, 3 ],
    [ 1, 2, 2 ],
    [ 1, 4 ],
    [ 2, 3 ],
    [ 5 ]
[/color]

Que je compare à magma qui fournit chaque partition sous forme décroissante (je pense qu'il y a une raison pour cela) et la famille des partitions d'un entier de manière décroissante relativement à l'ordre lexicographique

[color=#000000]
> P := Partitions(n) ;
> P ;
[
    [ 5 ],
    [ 4, 1 ],
    [ 3, 2 ],
    [ 3, 1, 1 ],
    [ 2, 2, 1 ],
    [ 2, 1, 1, 1 ],
    [ 1, 1, 1, 1, 1 ]
]
> L eq Sort([Reverse(p) : p in P]) ;
true
[/color]

Une question (qui fait que le fil risque d'être déplacé en informatique) : est ce que Python c'est le langage à la mode (depuis des années ?) qui est utilisé dans le cadre de l'enseignement, en initiation à l'algorithmique (lycée, collège, école primaire, maternelle) ? Et peut-être même dans certaines universités ? Du coup, on vit une époque formidable, non ?

Gilles old · February 2019

Bonjour Claude, et merci de t'intéresser à ce fil. Je n'ai pas eu le temps d'explorer le travail de Jérôme Kelleher, mais j'ai cru comprendre que les partitions descendantes se programmaient avec un poil plus de boulot. Regarde page 147, et puis page 179 quand il compare ses deux algorithmes "accélérés".

Je n'ai pas de connaissance sur l'ordre lexicographique, je vais me plonger là-dedans. Je n'ai pas résisté au plaisir (et surtout parce que je n'ai que ça sous la main) de programmer en Python ton algorithme. Il m'a fallu décrypter ton code (du Magma ?) et je n'ai pas compris à quoi sert la ligne

assert #b eq k+q-1  and   &+a eq &+b   and  Sort(b) eq b ;

mais elle n'a pas l'air bien importante, en tout cas Python s'en passe bien.

Python est à la mode, et je comprends pourquoi : gratuit, une syntaxe très légère et agréable à lire, gestion des grands entiers, pour rien au monde je ne reviendrais en arrière pour mes modestes besoins... De temps en temps j'ouvre des codes Maple que j'avais tapés il y a quelques années, j'ai la nausée quand je vois la complexité de la syntaxe. De plus il existe un grand nombre de librairies pour les besoins spécifiques. Je ne parle là que de l'usage mathématique.
J'enseigne en BTS SIO, c'est le langage choisi par les profs d'info ; en prépa je ne pense pas que beaucoup d'enseignants utilisent autre chose que Python de nos jours.

def successeur(a):
    k=len(a)
    if k==1:
        return a
    y=a[k-1]-1
    x=a[k-2]+1
    q=y//x
    b=a[:k-2]+q*[x]+[y-(q-1)*x]
    return b

def partitions(n):
    a=n*[1]
    L=[a]
    while a!=[n]:
        a=successeur(a)
        L+=[a]
    return L

>>> partitions(5)
[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 4], [2, 3], [5]]

claude quitté · February 2019

@Gilles
Je vais essayer d'en dire plus. Hier j'ai posté TROP vite et j'ai vu une coquille dans l'un de mes commentaires. Comme pour moi, les commentaires c'est ce qu'il y a de plus important, je reviens dessus en donnant un peu plus d'explications :

[color=#000000]
Successeur := function(a)
  // a est une partition de n (croissante au sens large)
  // Retourne la partition b de n, successeur de a dans l'ordre lexicographique
  // Exception : si la longeur k de a est 1 i.e. a = [n], retourne a.
  assert Sort(a) eq a ;
  k := #a ;
  if k eq 1 then return a ; end if ;
  // Utilisation les deux derniers éléments de a pour fabriquer la partition b
  y := a[k] - 1 ;
  x := a[k-1] + 1 ;
  // Division euclidienne : y = q*x + r
  // b est constituée des k-2 premiers éléments de a, suivie de x, .., x (q fois) puis de x+r
  // Ainsi b est bien croissante. 
  // Somme au delà de l'indice k-2 : a -> x+y, b -> q*x + x+r. C'est la même car x+y = q*x + x+r
  q, r := Quotrem(y,x) ; // y = q*x + r
  // b = a[1..k-2] \/  [x,x, .., x (q fois)] \/ [x + r] de longueur (k-2) + q + 1 = k-1+q
  b := a[1..k-2] cat [x^^q] cat [x + r] ;
  // On vérifie la longueur de b, sa somme et sa croissance
  assert #b eq k+q-1  and   &+a eq &+b   and  Sort(b) eq b ;
  return b ;
end function ;
[/color]

Mais il y a plusieurs choses que je voudrais faire comprendre, faire passer, sans que cela fasse trop polémique. D'abord je suis un vieux c.n (ça, c'est facile à comprendre). Ensuite, je suis parti de l'algorithme de l'auteur et je l'ai transformé ``via des opérations sûres''. Jusqu'à temps d'obtenir la fonction ci-dessus. Mais j'y ai passé un certain temps. Trop à mon goût et je juge cela ``anormal'' (de la part de l'auteur, cf plus loin).

Tu n'as pas oublié que dans ton premier post, tu as dit que tu ne comprenais pas ce que faisait l'algorithme. En y passant un certain temps (si j'ai bien compris). Pour moi, c'est absolument anormal (bis). Anormal de la part de l'auteur de fournir un tel algorithme (je sais bien qu'il explique ailleurs dans sa thèse ...etc.. mais je n'ai pas envie d'y aller voir). Un étudiant m'aurait remis un algorithme comme celui du premier post, la note assurée était 0 (rappel : je suis un veux c.n). Et s'il avait ajouté ``mais ça marche'', alors là ...

Ce que je dis sous-entend que la fonction que je donne ci-dessus est ``plus mieux'', plus claire ? Oui, car ce n'est pas difficile de faire mieux qu'un machin incompréhensible. Mais ce n'est pas du du tout le poins le plus important. Pour moi, le point le plus important, c'est qu'elle est spécifiée. Elle annonce l'objet qu'elle veut calculer/déterminer, à savoir la partition successeur (au sens lexicographique) de la partition donnée. Ainsi, s'il y a une erreur dans le code, c'est ``moins grave'' car j'ai annoncé ce que je voulais y faire.

Dit autrement, j'estime que l'algorithmique est une science à part entière. Et de la même manière qu'en mathématiques, on fait un gros effort pour fournir des énoncés et des preuves les plus clairs possibles, on doit en faire (à mon avis) autant en algorithmique. Pour mieux comprendre, il conviendrait d'évoquer la période des années 1970-1980 avec les grands auteurs (dans le désordre, Knuth, Dijkstra, Hoare, Wirth, ...etc...). Nous sommes bientôt en 2020 : quid de l'enseignement de l'algorithmique dans le secondaire ? C'est une vraie question (rappel : je n'y ai jamais enseigné et d'ailleurs je n'enseigne plus). Au fait, comment en est-on venu à introduire l'algorithmique dans le secondaire (G.D. ?). Vaste débat.

Gilles old · February 2019

@Claude.
J'ai regardé de plus près l'ordre lexicographique auquel je ne m'étais jamais intéressé jusqu'à aujourd'hui et je me suis attaché à justifier le bien-fondé du calcul du successeur d'une partition.

Soit $a=(a_1,a_2, \dots, a_k)$ une partition croissante de $n$. Posons $y=a_k-1 \geq 0$, $x=a_{k-1}+1$ et $q$ le quotient de $y$ par $x$, on a donc $y=qx+r$ avec $0\leq r <x$.
Soit $b=\left(a_1,a_2, \dots, a_{k-2}, \underbrace{x,x , \dots ,x}_{q \text{ fois}},x+r\right)$. Alors $b$ est une partition croissante de $n$ et strictement supérieure à $a$ car

$x>a_{k-1}\geq a_{k-2}$ et $x+r \geq x$ ;
$\underbrace{x+x + \dots +x}_{q \text{ fois}}+x+r=qx+x+(y-qx)=x+y=a_{k-1}+a_{k}$.

Là où j'ai un peu plus de mal c'est à justifier proprement qu'il n'y a pas de partition strictement comprise entre $a$ et $b$. Voilà ce que je propose, je ne sais pas si c'est ainsi que l'on doit raisonner.
Soit $c$ une partition vérifiant $a\leq c \leq b$, je veux montrer que $c \in \{a;b\}$. Elle s'écrit $c=(a_1,\dots,a_{k-2},c_1,c_2,\dots c_{p})$.
En éliminant les $k-2$ premiers termes communs, on a $(x-1,y+1)\leq (c_1,c_2,\dots c_p)\leq (x_1,x_2,\dots,x_q,x+r)$ où j'ai posé $x_i=x$ pour $1\leq i \leq q$ pour faciliter le comptage. La somme des termes de chacune de ces 3 listes vaut $x+y$, et on a $c_1 \in \{x-1 ; x\}$.

Si $c_1=x-1$, alors $p\geq 2$, sans cela on aurait $c_1+\dots+ c_p=x-1<x+y$.
Vu que $a \leq c$, c'est que $y+1 \leq c_2$. Supposons $p \geq 3$. Alors $c_1+\dots c_p \geq (x-1)+(y+1)+1 > x+y$, contradiction. Ainsi $p=2$, puis $c_2=y+1$ et $a=c$.
Si $c_1=x$, on a $c_i= x$ pour $1 \leq i \leq q$, d'où $(c_{q+1},\dots c_p) \leq (x+r)$, avec $c_{q+1}+\dots +c_p = x+r$. Supposons $ p\geq q+2$, alors comme $c_{q+1} \geq x$ et $c_{q+2} \geq x$, on aurait $2x \leq c_{q+1} + c_{q+2} \leq c_{q+1} + \dots +c_{p} =x+r$, puis $x \leq r$, contradiction. Ainsi $p=q+1$, puis $c_{q+1}=x+r$ et $c=b$.

LEG · February 2019

Bonjour
@claude quitté:
c'est le problème majeur en informatique..on leur apprend à faire des programmes d'algorithmes, il n'en connaissent pas le fonctionnement, seul le résultat à l'arrivée compte, du moment que cela fonctionne...!

D'où des programmes d'algorithmes pourris..., inefficace , limité en temps et en mémoire; et dans la plupart des cas il faut les reprendre , les modifier et les retranscrire en C++ pour des raison d'efficacité et mémoire..

Alors qu'effectivement, il serait plus simple avant chaque fonction du programme, d'y inclure une petite ligne de ce que va faire la fonction qui suit....Ou simplement une petite explication de ce que va faire l'algorithme. Ce qui permettrait au programmeur de comprendre ce que va et doit faire l'algorithme....

Bonne continuation.

claude quitté · February 2019

@Gilles
Merci pour ton dernier post (tiré mais pas encore lu). Ce qui aurait pu être intéressant, c'est que je te raconte comment j'ai pu transformer l'algorithme initial en la fonction Successeur. Mais je crois que je n'ai pas le courage.

Ce n'est pas en faisant uniquement des print (mais j'en ai fait). C'est par exemple en réfléchissant à ``la partie utile'' de $a$. Pas facile à expliquer. Et en constatant qu'en fait, on part de $[1, 1, \cdots, 1]$ et pas de $[0,n,0,\cdots, 0]$ comme on pourrait le croire (on peut d'ailleurs se demander si l'auteur l'a fait exprès auquel cas, pour moi, c'est une astuce de m.rd. ou s'il ne l'a pas fait exprés). En regardant la boucle interne (deux boucles while imbriquées, c'est mortel), en comptant le nombre de pas de cette boucle, en plaçant des assertions, en ...etc... Plusieurs heures.

L'algorithmique ne consiste absolument pas à des astuces. Je pointe un papier célèbre de Knuth, https://dl.acm.org/citation.cfm?id=356640&dl=ACM&coll=DL

Gilles old · February 2019

Grâce à tes explications, j'ai compris ce que fait l'auteur. Il effectue la division euclidienne par soustractions successives. Vu qu'il ne connaît pas la taille de la partition qui suit, il est obligé d'initialiser avec la plus grande taille possible, il la tronque ensuite.
Cela donne une fonction successeur du type suivant.

def successeur_partition(a):
    k=len(a)
    if k==1:
        return a
    n=sum(a)
    b=a[:k-2]+[0 for k in range(n-k+2)]
    y=a[k-1]-1
    x=a[k-2]+1
    while y>=x:
        b[k-2]=x
        y-=x
        k+=1
    b[k-2]=x+y
    return b[:k-1]

Je n'ai pas l'impression qu'on gagne grand chose : pas d'efficacité dans les soustractions successives au lieu de la division euclidienne, et manipulation de liste de taille fixe qu'on tronque à la fin, l'espace en mémoire est plus important.

Je ne me suis pas encore penché du côté de l'initialisation $[0,n,0,\dots,0]$.

Gilles old · February 2019

Et finalement sans la fonction "successeur", ton algorithme devient.

def partitions_sans_successeurs(n):
    a=n*[1]
    L=[a]
    k=n
    while k>1:
        y=a[k-1]-1
        x=a[k-2]+1
        q,r=divmod(y,x)
        a=a[:k-2]+q*[x]+[x+r]
        k+=q-1
        L+=[a]
    return L

C'est très joli je trouve !

Malgré son code non commenté (:-D), Jerome Kelleher est l'auteur de l'algorithme de calcul de partitions le plus rapide connu, c'est le second proposé sur sa page.

claude quitté · February 2019

@Gilles
J'ai regardé ton post http://www.les-mathematiques.net/phorum/read.php?5,1769938,1770342#msg-1770342. J'ai juste vu une coquille à la ligne 3 : c'est $x = a_{k-1} + 1$ au lieu de $x = a_{k-2} + 1$.

Sinon, ok pour $a \le c \le b \Rightarrow c = a \text { ou } c = b$. Effectivement, c'est une bonne chose de se débarrasser des $k-2$ premières composantes.

Tout revient à étudier la partition $b$ successeur (pour l'ordre lexicographique) d'une partition $a = (s,t)$, avec $s \le t$, de longueur $2$. Faisons semblant de ne rien savoir : ci-dessous, je fais quelque chose d'informel pour (re)-trouver $b$.

1. Peut-on avoir $b = (s, \bullet, \cdots)$ ? En réfléchissant un peu, on voit que NON (car $\bullet$ doit être $\ge t$ et la conservation de la somme fait que ..)

2. On tente donc $b$ sous la forme $b = (s+1, \cdots, \cdots)$. Et ce qui peut paraître étonnant, c'est que cela va réussir de manière assez simple. Bien sûr, $s+1$ ici, c'est ton $x$. Note : j'aime bien voir le dernier terme de $b$ sous la forme $x + r$ plutôt que $y - (q-1)x$, question de goût.

Voilà, voilà. On a donc les idées plus claires sur ce fameux algorithme.

Gilles old · February 2019

Merci Claude pour ta relecture. Je préfère également $x+r$, c'est d'ailleurs ainsi qu'il apparaît naturellement.

Algorithme pour partitions d'un entier

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 12