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

Question

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 haben alle einzigartige Höhen, vorausgesetzt die Werte 100-199cm sind.
3. Sie wollen 10 Gruppen bauen, die jeweils aus 1-99 Kinder.
4. Wie können Sie alle Gruppen bauen, während die Kinder müssen durch ihre Höhe sortiert werden?
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 in Gruppen aufgeteilt und alle Lösungen für diese 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, dass Sie mir helfen können. Vielen Dank im Voraus!

PS: Es ist keine Hausaufgaben. ;) Normalerweise brauche ich eine Funktion, die dies mit Zahlen tut. Aber ich konnte es nicht beschreiben abstrakt wie „Aufbau k Gruppen von Zahlen, während alle Nummern sortiert sind“. Ich dachte, Sie würden es auf diese Weise nicht verstehen. :) Eine Lösung in PHP wäre am besten, aber ich würde mich freuen, Lösungen auch in anderen Sprachen zu sehen. :)

Answer 1

Wie ich es verstehe, Sie fragen, effektiv nach Möglichkeiten, um das Intervall Partitionierung [100199] in 10 Teile, dh Sie wollen Zahlen finden x [0], ..., x [10], so dass:

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

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

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

}

Die 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 ist nicht schwer zu   findet eine Konstellation.

Normalerweise gibt 100! Wege 100 Artikel permutieren, aber da Sie bestellen sind die Erhaltung, können Sie Ihre Problemgröße nach unten im Wesentlichen reduzieren. Was Sie beschreiben, ist ein integer Partitionieren Problem . Zum Beispiel, sagen wir mal die Nummer 5 in alle möglichen ganzzahligen Teilmengen wurden Partitionierung, die bis 5 aufaddieren, dann würden Sie die Sätze bekommen {5}, {4, 1}, {3, 2}, {3, 1, 1 ,}, {2, 2, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1}.

Die Anzahl der Integer-Partitionen wächst exponentiell mit der Größe der ganzen Zahl, aber das exponentielle Wachstum langsam genug ist, dass Sie durch alle Partitionen von n = 100 aufzählen können, da es nur 190.569.292 von ihnen ist. Die zusätzliche Einschränkung ist, dass Sie alle Ihre Partitionen für Sets mit genau 10 Elemente filtern wollen, die durch Verwendung eines Ferrer Diagramm leicht aufzuzählen ist.

I kann durch eine Trennwand Ferrer Diagramm zeigen die Nummer 20 in 3 Schaufeln: mit einem 20 x 3 col Zeilenraster beginnen wie folgt:

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

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

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

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

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

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

Jetzt haben wir {16, 3, 1}. Weiter geht es auf diese Weise, bis Sie alle Permutationen haben aufzählen (seine bis zu Ihnen, ob {17, 1, 2} ist eine deutliche Partition von {17, 2, 1}).

Von diesem Punkt sollten Sie in der Lage sein, den allgemeinen Rahmen des Algorithmus zu vergegenwärtigen Sie brauchen - das heißt, wenn Sie die Herausforderung des Schreibens dieser Funktion von Grund auf neu möchten. Andere Leute haben bereits geschrieben viele effiziente Funktionen das Problem zu lösen leicht.