Combinatoria: Construcción de 10 grupos de 100 elementos mientras que los elementos permanecen ordenados

Question

Tengo un problema relacionado con la combinatoria. Por desgracia, no puedo describirlo de manera abstracta así que trato de explicarlo como una historia. :)

Problema:

1. Hay 100 niños en el patio del colegio.
2. Todos ellos tienen alturas únicas, suponiendo que los valores son 100-199cm.
3. Usted quiere construir 10 grupos, cada uno compuesto de 1-99 niños.
4. ¿Cómo se puede construir todos los grupos, mientras que los niños deben ser ordenados por su altura?
5. Necesito todas las soluciones posibles para estos grupos ya que no es difícil encontrar uno constelación.

corto y sencillo:

Todos los 100 niños de pie al lado del otro. Sólo tiene que decidir dónde se dividió en grupos y encontrar todas las soluciones para esto.

Ejemplo (los valores son las alturas):

[120 ... 190 ... 199] ... [126 ... 137 ... 144 ... 188] no es posible

[101] ... [104 ... 105 ... 112 ... 149] ... [169 ... 189] es posible

Espero que me puedan ayudar. Muchas gracias por adelantado!

PS: No es ninguna tarea. ;) Por lo general, necesito una función que hace esto con los números. Pero no podía describir esta manera abstracta como "k grupos de números de la construcción, mientras que todos los números están ordenados". Pensé que no lo entendería esta manera. :) Una solución en PHP sería mejor, pero yo estaría contento de ver soluciones en otros idiomas también. :)

Answer 1

A mi entender, que están pidiendo con eficacia la manera de dividir el intervalo [100199] en 10 partes, es decir, que desea encontrar los números x [0], ..., x [10] tal que:

x[0] = 100 < x[1] < x[2] < ... < x[9] < x[10] = 199

Definir un partition(intervalSize, pieces) función recursiva que cuenta el número de maneras de particiones en un intervalo dado. Que está después partition(100, 10).

El siguiente código Java cuenta las particiones (lo siento, no sé PHP que también):

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));     
    }

}

El siguiente código Java imprime las particiones reales. Debido a que el número de particiones es tan alto para (100,10), que estoy ilustrando la respuesta para (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 salida es:

|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

  

Necesito todas las soluciones posibles para   estos grupos ya que no es difícil de   encontrar una constelación.

Normalmente, hay 100! maneras de permutan 100 elementos, pero ya que estás preservar el orden, puede reducir el tamaño de su problema abajo sustancialmente . Lo que usted describe es una número entero de partición problema . Por ejemplo, digamos que estabas particionando el número 5 en todos los posibles subconjuntos de números enteros que suman 5, se obtendría los conjuntos {5}, {4, 1}, {3, 2}, {3, 1, 1 ,}, {2, 2, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1}.

El número de particiones enteros crece exponencialmente con el tamaño del número entero, pero el crecimiento exponencial es lo suficientemente lento que se puede enumerar todas las particiones de n = 100, ya que no solamente 190.569.292 de ellos son. La restricción adicional es que desea filtrar todas las particiones de conjuntos que contienen exactamente 10 artículos, lo cual es fácil de enumerar usando un diagrama de Ferrer.

I puedo demostrar un diagrama Ferrer por partición el número 20 en 3 cubos: comenzar con un 20 col x 3 fila de la cuadrícula como sigue:

 12345678901234567890
1******************
2*
3*

Por lo tanto, la primera partición es {18, 1, 1}

Ahora mover un elemento de la parte superior de la pila en la siguiente ranura:

 12345678901234567890
1*****************
2**
3*

Nuestra nueva partición es {17, 2, 1}. Podemos otro artículo de una pila a la otra:

 12345678901234567890
1****************
2***
3*

Ahora tenemos {16, 3, 1}. Se continúa de esta manera hasta que haya enumerar todas las permutaciones (su hasta usted si {17, 1, 2} es una partición distinta de {17, 2, 1}).

A partir de este punto, usted debería ser capaz de imaginar el esquema general del algoritmo que necesita - es decir, si desea que el reto de escribir esta función a partir de cero. Otras personas ya tienen un montón de funciones escritas eficientes para resolver el problema facilidad.