Combinatoire: Construire 10 groupes de 100 éléments tandis que les éléments restent classés

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:

1. Il y a 100 enfants sur la cour d'école.
2. Ils ont des hauteurs uniques, en supposant que les valeurs sont 100-199cm.
3. Vous voulez construire 10 groupes, chacun composé de 1-99 enfants.
4. Comment peut-on construire tous les groupes tandis que les enfants doivent être classés par leur hauteur?
5. 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. :)

Answer 1

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,

Answer 2

  

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.