Problème sur les partitions d'entiers — Les-mathematiques.net The most powerful custom community solution in the world

Problème sur les partitions d'entiers

Bonjour,

Soit $\mathcal{P}_{mn}$ l'ensemble des partitions $\kappa$ d'entiers telles que $|\kappa|\leq m$ et $\kappa$ a au plus $n$ parties (i.e. $\kappa_{n+1} = 0$). Je cherche à numéroter ces partitions $1$, $2$, $\ldots$, $\#\mathcal{P}_{mn}$. C'est-à-dire que je veux construire une bijection $\mathcal{P}_{mn} \to \{1, \ldots, \#\mathcal{P}_{mn}\}$ (éventuellement récurrente). Une idée ?

Réponses

  • J'ai ça dans un article à ce propos mais je ne comprends pas.89004
  • Exemple pour $m=4$ et $n=3$, de ce que je comprends.

    $N_{(1)} = 1$, $N_{(2)} = 2$, $N_{(3)} = 3$, $N_{(4)} = 4$,

    $N_{(1,1)} = 5$, $N_{(2,1)} = 6$, $N_{(2,2)} = 7$, $N_{(3,1)} = 8$,

    $N_{(1,1,1)} = 9$, $N_{(2,1,1)} = 10$.

    Je ne comprends rien à cette histoire de $D$.
  • Apparemment ce code fait ça. Mais je n'y comprends rien pour l'instant.
  • Le $D$ du numéro d'une partition $\kappa$ donne le numéro du premier fils de $\kappa$.

    Dans ton exemple $D(1)=5$, $D(2)=6$, $D(3)=8$, $D(5)=9$, $D(6)=10$.
  • Merci. Mais j'ai compris ça, mais ça ne me suffit pas. J'essaye d'implémenter l'algorithme 4.2 de cet article. Il marche (modulo quelques corrections) quand je rentre à la main les $N_\kappa$ pour un certain $m$. Je ne comprends pas le "Compute $N_\mu$ using 4.1".
  • Ben, le 4.1 est une formule de récurrence pour calculer $N_\mu$. Ce qui est un peu compliqué, c'est de fabriquer le dictionnaire $D$, mais ça peut se faire. Je vois en gros comment on pourrait écrire ça en Python par exemple, mais je ne vais pas le faire car ça me prendrait un peu de temps.
  • Finalement ça ne m'a pas pris beaucoup de temps.

    En Python 3, code pour fabriquer le dictionnaire D (et compter le nombre de partitions non vides) :
    def Dicpart(m,n) :
        D={}
        Last=[[0,m,m]]
        fin=0
        for i in range(n) :
            NewLast=[]
            for record in Last :
                num=record[0] ; manque=record[1] ; der=record[2]
                l=min(manque,der)
                if l>0 : D[num]=fin+1
                NewLast+=[[fin+i+1,manque-i-1,i+1] for i in range(l)]
                fin=fin+l
            Last=NewLast
        return D,fin
    

    On applique sur un cas déjà vu :
    Dicpart(4,3)
    
    ({0: 1, 1: 5, 2: 6, 3: 8, 5: 9, 6: 10}, 10)

    Maintenant on peut définir le N :
    m=10 ; n=7 
    D,nb=Dicpart(m,n)
    
    def Num(k) : 
        if k==[] : return 0
        else : return D[Num(k[:-1])]+k[-1]-1
        # C'est la formule (4.1)
    

    Voyons voir :
    print("nb de partitions non vides",nb)
    k=[3,2,2,1,1]
    print("Numéro de",k,":",Num(k))
    
    nb de partitions non vides : 131
    Numéro de [3, 2, 2, 1, 1] : 102

    Vérifions que le dernier est bien celui qu'on pense
    k=[4,1,1,1,1,1,1]
    print("Numéro de",k,":",Num(k))
    
    Numéro de [4, 1, 1, 1, 1, 1, 1] : 131
  • Merci infiniment GaBuZoMeu !

    Je ne connais pas Python mais je me débrouille pour le traduire en R.

    Tu es sûr que tu as bien recopié la sortie de Dict(4,3). On devrait trouver ça :

    $D(1)=5$, $D(2)=6$, $D(3)=8$, $D(5)=9$, $D(6)=10$.

    C'est bien ce que je trouve avec ma trad de ton code:
    > Dicpart(4,3)
    [1]  1  5  6  8 NA  9 10
    

    Mais toi tu as autre chose.
  • Tu as dû mal lire. C'est bien exactement ce que j'ai, y compris l'entrée 0:1 qui dit que le premier fils de la partition vide [] (n° 0) est [1] (n°1).
    Ma procédure Dicpart retourne un couple formé du dictionnaire lui-même et du nombre de partitions non vides.
    Par contre, je ne comprends pas ce qu'est le [1] que tu as au début.
  • Ah ok, oui mais j'ai mal lu. Le [1] est un truc que R affiche, ce n'est rien.
  • Grrr ça marche avec R, mais je n'arrive pas à programmer l'algo en Haskell. Quelqu'un de chaud pour le faire en Haskell ?
  • C'est bon, je l'ai fait en Haskell :-) Mais j'ai finalement utilisé des variables mutables.

    Pour info il existe une version plus performante de cet algo, programmé en C + matlab, plus performant car qui n'utilise pas de récurrence. Le code est disponible mais pas l'explication de l'algo.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!