Combinatorics: Costruire 10 gruppi di 100 elementi mentre gli elementi rimangono ordinati

Question

Ho un problema di calcolo combinatorio. Purtroppo, non posso descriverlo astrattamente così cerco di spiegare come una storia. :)

Problema:

1. Ci sono 100 bambini in cortile della scuola.
2. Tutti hanno altezze uniche, assumendo i valori sono 100-199cm.
3. Si vuole costruire 10 gruppi, ciascuno composto da 1-99 bambini.
4. Come si può costruire tutti i gruppi, mentre i bambini devono essere ordinati secondo la loro altezza?
5. ho bisogno di tutte le soluzioni possibili per questi gruppi perché non è difficile trovare una costellazione.

Breve e facile:

Tutti i 100 bambini fianco a fianco. Dovete solo decidere dove li divise in gruppi e trovare tutte le soluzioni per questo.

Esempio (valori sono altezze):

[120 ... 190 ... 199] ... [126 ... 137 ... 144 ... 188] non è possibile

[101] ... [104 ... 105 ... 112 ... 149] ... [169 ... 189] è possibile

Spero che mi può aiutare. Grazie mille in anticipo!

PS: Non è un lavoro. ;) Normalmente, ho bisogno di una funzione che fa con i numeri. Ma non potevo descrivere questo astrattamente come "la costruzione di gruppi di numeri k, mentre tutti i numeri sono ordinati". Ho pensato che non avresti capito in questo modo. :) Una soluzione in PHP sarebbe meglio, ma sarei felice di vedere soluzioni in altre lingue. :)

Answer 1

Se ho capito bene, si sta effettivamente chiedendo di modi di partizionamento dell'intervallo [100.199] in 10 parti, vale a dire che si desidera trovare i numeri x [0], ..., x [10] in modo tale che:

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

definire una funzione partition(intervalSize, pieces) ricorsiva che conta il numero di modi per partizionare un dato intervallo. Tu sei dopo partition(100, 10).

Il seguente codice Java conta le partizioni (mi dispiace, non so PHP che bene):

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

}

Il seguente codice Java stampa le partizioni attuali. Poiché il numero di partizioni è così alta per (100,10), sto illustrando la risposta per (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);
    }
}

L'output è:

|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

  

ho bisogno di tutte le soluzioni possibili per   questi gruppi dato che non è difficile   trovare una costellazione.

Normalmente, ci 100! modi per permutare 100 elementi, ma dal momento che stai ordine preservare, è possibile ridurre la dimensione del problema verso il basso sostanzialmente . Quello che stai descrivendo è un intero partizionamento problema . Per esempio, diciamo che si effettuavano una compartimentazione del numero 5 in tutte le possibili sottoinsiemi interi che si sommano a 5, si otterrebbe i set {5}, {4, 1}, {3, 2}, {3, 1, 1 ,}, {2, 2, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1}.

Il numero di partizioni intere cresce esponenzialmente con la dimensione del numero intero, ma la crescita esponenziale è abbastanza lento che è possibile enumerare tutte le partizioni di n = 100, dal momento che solo 190.569.292 di loro ci sono. Il vincolo ulteriore è che si desidera filtrare tutte le partizioni per i set che contengono esattamente 10 elementi, che è facile enumerare attraverso l'utilizzo di uno schema di Ferrer.

posso dimostrare un diagramma Ferrer per partizione il numero 20 in 3 benne: iniziare con una griglia 3 x riga 20 col come segue:

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

Quindi, la prima partizione è {18, 1, 1}

Ora spostare un elemento dalla cima della pila nello slot successivo:

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

La nostra nuova partizione è {17, 2, 1}. Siamo in grado di un altro elemento da una pila all'altra:

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

Ora abbiamo {16, 3, 1}. Si continua in questo modo fino a quando hai enumerare tutte le permutazioni (il suo fino a voi se {17, 1, 2} è una partizione diversa da {17, 2, 1}).

Da questo punto, si dovrebbe essere in grado di immaginare il quadro generale dell'algoritmo è necessario - che è, se si desidera la sfida di scrivere questa funzione da zero. Altre persone hanno già sacco scritte di funzioni efficienti per risolvere il problema facilmente.