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 ?
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 ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
$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$.
Dans ton exemple $D(1)=5$, $D(2)=6$, $D(3)=8$, $D(5)=9$, $D(6)=10$.
En Python 3, code pour fabriquer le dictionnaire D (et compter le nombre de partitions non vides) :
On applique sur un cas déjà vu : ({0: 1, 1: 5, 2: 6, 3: 8, 5: 9, 6: 10}, 10)
Maintenant on peut définir le N :
Voyons voir : 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 Numéro de [4, 1, 1, 1, 1, 1, 1] : 131
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:
Mais toi tu as autre chose.
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.
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.