Je me gratte la tête en essayant de le faire et ça me mange. Je sais que ce n'est pas ce complexe. J'ai un certain nombre d'articles, ce nombre peut être égal ou supérieur à trois. Ensuite, j'ai besoin de déterminer la combinaison possible de groupe d'éléments qui complèteront le total. La seule restriction qu'il est que les groupes devraient avoir trois éléments ou plus, ne pas dépasser (mais incluant) sept articles.
Par exemple: P>
Si j'ai 7 articles, je pourrais alors avoir ces groupes possibles: p>
Si j'ai 12 articles, je pourrais avoir ces groupes possibles: p>
J'ai pensé à la récursion et j'ai commencé à mettre en œuvre l'algorithme. Cela ne fonctionne évidemment pas. Je suce à la récursion. Beaucoup. P>
//Instance Fields
public List<ArrayList<String>> options;
//Method that will generate the options. The different options are
//stored in a list of "option". An individual option will store a list of
//strings with the individual groups.
public void generateOptions(int items, ArrayList<String> currentOption){
//If the current option is null, then create a new option.
if(currentOption == null){
currentOption = new ArrayList<String>();
}
if(items < 3){
//If the number of items is less than three then it doesn't comply with the
//requirements (teams should be more or equal than three.
currentOption.add("1 group of "+items+" items");
options.add(currentOption);
}
else{
//I can make groups of 3,4,5,6 and 7 items.
for(int i = 3;i<=7;i++){
if(items%i == 0){
// If the number of items is divisible per the current number,
// then a possible option could be items/i groups of i items.
// Example: Items = 9. A possible option is 3 groups of 3 items.
currentOption.add(items/i +" groups of "+ i+" items");
options.add(currentOption);
}
else{
// If the number of items - the current number is equal or greater than
// three, then a possible option could be a group of i items
// and then I'll have items-i items to separate in other groups.
if(items - i >=3){
currentOption.add("1 group of "+i+" items");
generateOptions(items-i,currentOption);
}
}
}
}
}
6 Réponses :
Ce serait le nombre de Partitions de N contenant uniquement des entiers de l'ensemble [3,7]
similaire au problème de la partition ordinaire (où les éléments peuvent être un entier positif):
http://www.research.att.com/~njas/frences/A000041
Je ne vois pas Une séquence de numéro existante qui correspond exactement à cette contrainte, mais vous pouvez compter les groupes comme (en python). Cela peut prendre une plage arbitraire ([3,7] dans ce cas) et compter tout le A, B, C, D, E (3 * A + 4 * B + 5 * C + 6 * D + 7 * E) Séquences qui somme à n. vous auriez: ou @ Cletus's excellente solution
Cela peut être fait avec la récursion. Vous ne dites pas si vous voulez juste que le nombre de possibilités ou les possibilités réelles.
Une chose que vous voulez faire est d'éviter la répétition de sens ne compte pas 4 et 3 aussi comme 3 et 4. Une façon de le faire est Pour créer des séquences de tailles de groupe non descendantes.
probablement la meilleure structure de données pour cela est un arbre: puis pour trouver le nombre de combinaisons Vous comptez simplement les nœuds de feuilles. Pour trouver les combinaisons réelles, vous venez de marcher sur l'arbre. L'algorithme de construction d'un tel arbre va quelque chose comme ceci: ou quelque chose de très proche de cela.
i à partir de Taille vers le bas de minsize ;
i ;
j à partir de minisize à i qui est inférieur ou égal à i i
j
Jung [ Jung.sourceforge.net/doc /API/EDU/UCI/ICHS/JUNG/GRAPH/TREE.HT ML] a une implémentation d'arbres qui peut aider.
Je pense que je comprends cela, mais où sont les 2 groupes de 6 et 6 représentés dans cette structure de données? Si la branche 6 à 6 et les 6 à 3 à 3, devraient-elles le mal comprendre?
En outre, Harschware's Jung URL a une traînée], on dirait que cela devrait être
Merci! Oui, j'ai besoin des combinaisons elles-mêmes, pas du nombre. J'essaye ça. Merci.
Je pense que je manque quelque chose dans votre pseudocode. Où puis-je sauter de 12 à 9 dans la première itération?
@MiguuRios: Vous sautez de 12 à 9 car à 11 heures, vous appelez à nouveau la fonction avec une taille de 1, qui est inférieure à la taille minimale afin qu'elle ne génère aucun arbre. C'est la partie de l'algorithme qui va de minsize à i .
Un arbre est le meilleur moyen d'y penser, mais vous pouvez utiliser une récursive pour en construire un sans faire explicitement un arbre. Vous pouvez penser à la racine comme votre total. Utilisation des groupes de taille 3-7, vous devez trouver une combinaison de groupes qui résume jusqu'à votre total.
Vous pouvez utiliser 0 groupes de 7, 1 groupe de 7, 2 groupes de 7, etc. pour chacun de ces Valeurs, vous pouvez utiliser 0 groupes de 6, 1 groupe de 6, etc. Le premier niveau de votre arbre représentera combien de 7 ont été utilisés. Le deuxième niveau est combien de 6 ont été utilisés, etc. Lorsque vous utilisez X 7, vous devez trouver combien de combinaisons de 6, 5, 4, 4, et 3, vous pouvez utiliser pour résumer jusqu'à (Sum-X * 7) , et ainsi de suite pour chaque niveau inférieur (appel récursif).
Votre arbre aura toujours 5 niveaux.
Utilisation de la récursivité pour construire l'arborescence, voici un petit échantillon de code Python (sans tentative de tailler l'arbre, il explorera toute la chose). cette sortie:
Voici un algorithme (exprimé en C ++) pour résoudre une version plus générale du problème,
Avec des limites supérieure et inférieure arbitraire sur les adverses pouvant apparaître dans chaque partition: et une sortie d'échantillon:
C'est très proche de ce que je cherche. J'essaie de le convertir en Java pour voir comment cela fonctionne. Merci.
en pseudocode:
List<String> results;
void YourAnswer(int n) {
GeneratePossiblities("", [3, 4, 5, 6, 7], n);
}
void GeneratePossibilities(String partialResult, List<int> buildingBlocks, int n) {
if (n == 0) {
// We have a solution
results.Add(partialResult);
} else if (buildingBlocks.IsEmpty()) {
// Dead-end: there is no solution that starts with the partial result we have and contains only the remaining building blocks
return;
} else {
int first = buildingBlocks.First();
buildingBlocks.PopFirst();
for (int i = 0, i < n/first; i++) {
GeneratePossibilities(partialResult + " " + i + "groups of " + first,
buildingBlocks,
n - i * first);
}
}
}
Qu'est-ce que vous décrivez est une version moins générale du Fonction de partition . Les algorithmes déjà donnés sont ridiculement compliqués, voici un peu plus simple (en pseudo-code, je vous laisserai à vous de traduire en java :) ) < Pré> xxx
Celui-ci ne me donnera que le nombre de partitions. J'ai aussi besoin des partitions eux-mêmes. Merci!