Kombinatorik: Gebäude 10 Gruppen von 100 Elementen, während Elemente

Question

sortieren bleiben Ich habe ein Problem in Bezug auf Kombinatorik bekommt. Leider kann ich es nicht abstrakt beschreiben, also versuche ich es als eine Geschichte zu erklären. :)

Problem:

1. Es gibt 100 Kinder auf dem Schulhof.
2. Sie alle haben einzigartige Höhen, vorausgesetzt die Werte 100-199cm sind.
3. Sie möchten 10 Gruppen erstellen, die jeweils aus 1-99 Kindern bestehen.
4. Wie können Sie alle Gruppen erstellen, während die Kinder nach ihrer Größe sortiert werden müssen?
5. Ich brauche alle möglichen Lösungen für diese Gruppen, da es nicht schwer ist, eine Konstellation zu finden.

Kurz und einfach:

Alle 100 Kinder stehen nebeneinander. Sie müssen nur entscheiden, wo Sie sie in Gruppen aufteilen und alle Lösungen dafür finden.

Beispiel (Werte sind die Höhen):

[120 ... 190 ... 199] ... [126 ... 137 ... 144 ... 188] ist nicht möglich

[101] ... [104 ... 105 ... 112 ... 149] ... [169 ... 189] ist möglich

ich hoffe, helfen kann mich. Vielen Dank im Voraus!

PS: Es ist keine Hausaufgaben. ;) Normalerweise brauche ich eine Funktion, die das mit Zahlen macht. Aber abstrakt kann ich das nicht beschreiben wie "k Gruppen von Zahlen bilden, während alle Zahlen sortiert sind". Ich dachte, du würdest es nicht so verstehen. :) Eine Lösung in PHP wäre am besten, aber ich würde mich freuen, auch Lösungen in anderen Sprachen zu sehen. :)

Answer 1

Wie ich es verstehe, fragen Sie effektiv nach Möglichkeiten der Partitionierung des Intervalls [100,199] in 10 Teile, dh Sie wollen Zahlen x [0], ..., x [10] finden, so dass:

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

definieren eine rekursive Funktion partition(intervalSize, pieces), die die Anzahl der Möglichkeiten zählt ein gegebenes Intervall zu partitionieren. Sie sind nach partition(100, 10).

Die folgende Java-Code zählt die Partitionen (sorry, weiß nicht, PHP, dass gut):

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

} 

den folgenden Java-Code druckt die aktuellen Partitionen.Da die Anzahl der Partitionen so hoch (100,10) ist, ich veranschauliche die Antwort für (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); 
    } 
} 

Die Ausgabe lautet:

 
|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

Ich brauche alle möglichen Lösungen für diese Gruppen, da es nicht schwer ist eine Konstellation zu finden.

Normalerweise 100! Möglichkeiten, 100 Elemente zu permutieren, aber da Sie die Reihenfolge beibehalten, können Sie Ihre Problemgröße reduzieren im Wesentlichen. Was Sie beschreiben, ist ein integer partitioning problem. Angenommen, Sie haben die Nummer 5 in alle möglichen Integer-Teilmengen partitioniert, die sich zu 5 addieren, erhalten Sie die Mengen {5}, {4, 1}, {3, 2}, {3, 1, 1 ,}, {2, 2, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1}. Die Anzahl der Ganzzahl-Partitionen wächst exponentiell mit der Größe der Ganzzahl, aber das exponentielle Wachstum ist langsam genug, dass Sie alle Partitionen von n = 100 aufzählen können, da es nur 190.569.292 davon gibt. Die zusätzliche Einschränkung besteht darin, dass Sie alle Ihre Partitionen nach Sets filtern möchten, die genau 10 Elemente enthalten. Dies ist durch ein Ferrer-Diagramm einfach aufzuzählen.

kann ich die Zahl 20 in 3 Eimer eine Ferrer Diagramm durch Partition zeigen: mit einer 20 col x 3 Reihen grid beginnen wie folgt:

 
123456789
1****************** 
2* 
3* 

So wird die erste Partition ist {18, 1, 1 }

Jetzt ein Element aus der Oberseite des Stapels in den nächsten Schlitz bewegen:

 
123456789
1***************** 
2** 
3* 

Unsere neue Partition ist {17, 2, 1}. Wir können ein anderes Element von einem Stapel zum anderen:

 
123456789
1**************** 
2*** 
3* 

Jetzt haben wir {16, 3, 1}. Sie fahren auf diese Weise fort, bis Sie alle Permutationen aufgelistet haben (es liegt an Ihnen, ob {17, 1, 2} eine eindeutige Partition von {17, 2, 1} ist).

Von diesem Punkt an sollten Sie in der Lage sein, sich den allgemeinen Überblick über den Algorithmus, den Sie benötigen, vorzustellen - das heißt, wenn Sie die Herausforderung haben möchten, diese Funktion von Grund auf neu zu schreiben. Andere Leute haben bereits written lots of efficient functions, um das Problem leicht zu lösen.