Combinatorics: Costruire 10 gruppi di 100 elementi mentre gli elementi rimangono ordinati
-
20-09-2019 - |
Domanda
Ho un problema di calcolo combinatorio. Purtroppo, non posso descriverlo astrattamente così cerco di spiegare come una storia. :)
Problema:
- Ci sono 100 bambini in cortile della scuola.
- Tutti hanno altezze uniche, assumendo i valori sono 100-199cm.
- Si vuole costruire 10 gruppi, ciascuno composto da 1-99 bambini.
- Come si può costruire tutti i gruppi, mentre i bambini devono essere ordinati secondo la loro altezza?
- 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. :)
Soluzione
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,
Altri suggerimenti
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.