une partition d'un entier positif n est une matrice non croissante d'entiers positifspartition des entiers
a [1], a [2], ..., a [m]
satisfaisant
a [1] + a [2] + ... + a [m] = n.
m est appelée la longueur de cette partition.
Nous pouvons lister toutes les partitions de n dans un ordre spécifié. Par exemple, si nous utilisons la règle par laquelle une lexicographie trie tous les mots anglais, cela s'appelle l'ordre lexicographique. Une autre façon, si nous utilisons la règle par laquelle le langage C compare les chaînes, cela s'appelle l'ordre lexicographique inverse. Et il y a aussi un ordre de colex.
Pour générer toutes les partitions d'un entier n, nous avons un algorithme bien proposé par Stojmenovic, qui a déjà été inclus dans le livre de Knuth.
Pour générer toutes les partitions de n avec exactement la longueur m, nous pouvons utiliser l'ordre de colex, cet algorithme est également inclus dans le livre de Knuth.
Pour générer toutes les partitions de n avec tous leurs éléments n'excédant pas k, nous pouvons utiliser l'algorithme en 1, en changeant simplement sa condition initiale et la condition de sortie du cycle.
Voici ma question: comment générer les partitions dont la longueur est exactement m et dont les éléments ne dépassent pas k?
Ici m et k sont des constantes. Bien entendu, une partition dont les éléments n'excèdent pas k est équivalente à son premier élément n'excédant pas k.
Oh, je pense que je l'ai résolu. pour
a [1] + a [2] + ... + a [m] n =
peut être écrit comme
(k + 1-a [1]) + (k + 1-a [2]) + ... + (k + 1-a [m]) = m (k + 1) -n
et le dernier est juste une partition inversée de m (k + 1) -n!
Si vous l'avez résolu, postez-le comme réponse et acceptez-le. (Je ne sais pas comment votre truc interdit les nombres négatifs, bien que je n'y ai pas beaucoup pensé.) – sdcvvc
Comment la partition de m (k + 1) -1 est-elle maintenue à une longueur fixe m? – Beta