Composition de n em> dans les pièces k em> Je veux énumérer toutes les compositions possibles de N dans les parties K - Quelqu'un a-t-il un algorithme (de préférence dans R)? Ou savoir si c'est dans la bibliothèque n'importe où? Par exemple, si j'ai n em> cubes, et k em> sacs et souhaitez répertorier toutes les dispositions possibles des cubes dans les sacs. par exemple. Vous pouvez organiser 3 cubes dans 2 sacs: P> (2, 0) (1, 1) (0, 2)
4 Réponses :
Compositions informatiques (j'ignore comment le terme standard est) et les combinaisons sont équivalentes dans un sens. Il y a une fonction bijective entre les combinaisons de En supposant que votre algorithme de combinaisons informatiques donne des combinaisons avec des "lettres commandées", le reste est un calcul trivial. en python: k + 1 dans n + k et compositions de n dans k pièces. Tout ce que l'on doit faire est d'attribuer un numéro de 1 à N à chaque lettre des combinaisons, commandez les lettres en fonction de leur numéro, puis:
Je ne suis pas un expert, je n'hésite donc pas à éditer la réponse, mais je crois que l'algorithme donné ici calcule Compositions faibles , plutôt que des compositions. La différence est que zéro est un élément possible d'une composition faible, mais pas d'une composition.
En fait, je pense que cet algorithme ne fonctionne pas du tout. Compositions (2, 3) Retourne un générateur sur, (0, 0, 0) (0, 0, 1) (0, 1, 0) (1, 0, 0) (0, 0 , 0) Ce sont pas les compositions de 2, et l'une d'elles est répétée!
Ce que vous essayez de lister est appelé un k em> -multicombination. Le problème est souvent indiqué de cette façon: donnée n indiscernable des balles em> et k em> les cases, répertoriez toutes les méthodes possibles de distribuer toutes les balles dans les cases. Le nombre de telles distributions est la suivante: pour plus d'arrière-plan, voir la méthode 4 du Dwelve-Fold Way . P> Voici le code pour énumérer les distributions (C ++): P> (5,0,0)
(4,1,0)
(4,0,1)
(3,2,0)
(3,1,1)
(3,0,2)
(2,3,0)
(2,2,1)
(2,1,2)
(2,0,3)
(1,4,0)
(1,3,1)
(1,2,2)
(1,1,3)
(1,0,4)
(0,5,0)
(0,4,1)
(0,3,2)
(0,2,3)
(0,1,4)
(0,0,5)
N'est-ce pas l'équation factorielle (n * k * 1) / (factorielle (k-1) * factorielle (n)) ? Je demande, parce que je viens d'apprendre des compositions faibles.
@MattMunson, l'équation était correcte pour un N -Multicombination, mais j'ai décrit un k -MultiCombination dans le texte. J'ai fait une autre modification pour refléter le changement.
Comme il m'a fallu un peu d'effort pour lire l'intention de la solution d'autre C ++, une traduction à Python (également en tant que générateur de générateur au lieu de la chaîne): test:
FWIW, j'ai ajouté Python 3 versions de votre code à Ma réponse qui utilise iTerTools.combinations Générer des partitions faibles.
J'ai fait la traduction de l'algorithme NexCom d'origine à la structure de Fortran et Java. La version Java est la suivante:
public void allCombinations(final int n, final int k) {
final int[] input = new int[k + 1];
Boolean mtc = Boolean.FALSE;
int t = n;
int h = 0;
do {
if (mtc) {
if (t > 1) {
h = 0;
}
h++;
t = input[h];
input[h] = 0;
input[1] = t - 1;
input[h + 1]++;
} else {
// First permutation is always n00...0 i.e. it's a descending
// series lexicographically.
input[1] = n;
for (int i = 2; i <= k; i++) {
input[i] = 0;
}
}
System.out.println(java.util.Arrays.toString(input));
mtc = input[k] != n;
} while (mtc);
}