Combinatoire: Construire 10 groupes de 100 éléments tandis que les éléments restent classés
-
20-09-2019 - |
Question
J'ai un problème en ce qui concerne combinatoires. Malheureusement, je ne peux pas le décrire abstraitement si je tente de l'expliquer comme une histoire. :)
Problème:
- Il y a 100 enfants sur la cour d'école.
- Ils ont des hauteurs uniques, en supposant que les valeurs sont 100-199cm.
- Vous voulez construire 10 groupes, chacun composé de 1-99 enfants.
- Comment peut-on construire tous les groupes tandis que les enfants doivent être classés par leur hauteur?
- J'ai besoin toutes les solutions possibles pour ces groupes car il est pas difficile de trouver une constellation.
Court et facile:
Les 100 enfants se tiennent côte à côte. Il vous suffit de décider où les diviser en groupes et de trouver toutes les solutions pour cela.
Exemple (les valeurs sont les hauteurs):
[120 ... 190 ... 199] ... [126 ... 137 ... 144 ... 188] est impossible
[101] ... [104 ... 105 ... 112 ... 149] ... [169 ... 189] est possible
J'espère que vous pouvez me aider. Merci beaucoup à l'avance!
PS: Il n'y a pas de devoirs. ;) Normalement, je besoin d'une fonction qui fait cela avec des chiffres. Mais je ne pouvais pas décrire ce abstraitement comme « la construction k groupes de chiffres alors que tous les numéros sont classés ». Je pensais que tu ne comprendrais pas cette façon. :) Une solution en PHP serait mieux, mais je serais heureux de voir des solutions dans d'autres langues. :)
La solution
Si je comprends bien, vous demandez efficacement des moyens de diviser l'intervalle [100199] en 10 parties, à savoir que vous voulez trouver les numéros x [0], ..., x [10] tel que:
x[0] = 100 < x[1] < x[2] < ... < x[9] < x[10] = 199
Définir une partition(intervalSize, pieces)
de fonction récursive qui compte le nombre de façons de partitionner un intervalle donné. Vous êtes après partition(100, 10)
.
Le code Java suivant compte les partitions (désolé, je ne sais pas PHP bien):
public class Partitions
{
static long[][] partitions = new long[100][10];
private static long partition(int intervalSize, int pieces)
{
if (partitions[intervalSize-1][pieces-1] != 0) {
return partitions[intervalSize-1][pieces-1];
}
long partition = 0L;
if (pieces == 1) {
partition = 1L;
} else {
for (int i = 1; i <= intervalSize - 1; i++) {
partition += partition(intervalSize - i, pieces - 1);
}
}
partitions[intervalSize-1][pieces-1] = partition;
return partition;
}
public static void main(String[] args)
{
System.out.println(partition(100, 10));
}
}
Le code Java suivant imprime les partitions réelles. Comme le nombre de partitions est si élevé pour (100,10), je suis illustrant la réponse pour (5,3):
public class Partitions2
{
private static void showPartitions(int sizeSet, int numPartitions)
{
showPartitions("", 0, sizeSet, numPartitions);
}
private static void showPartitions(String prefix, int start, int finish,
int numLeft)
{
if (numLeft == 0 && start == finish) {
System.out.println(prefix);
} else {
prefix += "|";
for (int i = start + 1; i <= finish; i++) {
prefix += i + ",";
showPartitions(prefix, i, finish, numLeft - 1);
}
}
}
public static void main(String[] args)
{
showPartitions(5, 3);
}
}
La sortie est la suivante:
|1,|2,|3,4,5, |1,|2,3,|4,5, |1,|2,3,4,|5, |1,2,|3,|4,5, |1,2,|3,4,|5, |1,2,3,|4,|5,
Autres conseils
J'ai besoin toutes les solutions possibles pour ces groupes car il est difficile de ne pas trouver une constellation.
Normalement, il y a 100 ans! façons de permutent 100 articles, mais comme vous préserver l'ordre, vous pouvez réduire la taille de votre problème vers le bas pas . Ce que vous décrivez est un de . Par exemple, disons que vous partitionner le numéro 5 dans tous les sous-ensembles entiers possibles qui ajoutent jusqu'à 5, vous obtiendrez les ensembles {5}, {4, 1}, {3, 2}, {3, 1, 1 ,}, {2, 2, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1}.
Le nombre de partitions entières connaît une croissance exponentielle avec la taille de l'entier, mais la croissance exponentielle est assez lent que vous pouvez énumérer toutes les partitions de n = 100, car il n'y a que 190.569.292 d'entre eux. La contrainte supplémentaire est que vous voulez filtrer toutes vos partitions pour ensembles contenant exactement 10 points, ce qui est facile à énumérer en utilisant un diagramme Ferrer.
Je peux montrer un schéma Ferrer par partition le nombre 20 en 3 seaux: commencer avec un col 20 x 3 grille de lignes comme suit:
12345678901234567890 1****************** 2* 3*
Ainsi, la première partition est {18, 1, 1}
Maintenant déplacer un élément à partir du haut de la pile dans la fente suivante:
12345678901234567890 1***************** 2** 3*
Notre nouvelle partition est {17, 2, 1}. Nous pouvons un autre élément d'une pile à l'autre:
12345678901234567890 1**************** 2*** 3*
Maintenant, nous avons {16, 3, 1}. Vous continuez de cette façon jusqu'à ce que vous avez énumérer toutes les permutations (son à vous si {17, 1, 2} est une partition distincte de {17, 2, 1}).
De ce point, vous devriez être en mesure d'envisager les grandes lignes de l'algorithme dont vous avez besoin - qui est, si vous voulez le défi d'écrire cette fonction à partir de zéro. D'autres personnes ont déjà beaucoup de fonctions écrites efficaces pour résoudre le problème facilement.