Intervalleinteilung < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:35 So 27.07.2008 | | Autor: | hoare |
| Aufgabe | | Keine exakte Aufgabenstellung vorhanden (hoffe ich darf hier trotzdem posten) |
Was ich suche ist eine Mathematische Formel / Herangehensweise, wie ich folgendes lösen kann:
Gegeben habe ich eine sortierte Folge von natürlichen Zahlen aus einem festen Intervall. Diese Zahlen möchte ich nun aufsteigend in n Gruppen aufteilen und zwar so, dass alle Gruppen möglichst gleich viele Werte enthalten.
Es geht also darum, wo ich die Grenzen setzen muss.
Ein Beispiel macht die sache hoffentlich deutlicher:
Sei n=2 also zwei Gruppen.
Sei die Zahlenfolge: 1, 3, 5, 7, 9, 10
Hier sollte die Granze demnach bei 5 liegen.
Gruppe A enthält also die Elemente (1, 3, 5) und Gruppe B (7, 9, 10)
Bei drei Gruppen wäre die Verteilung dementsprechend (1, 3) (5, 7) (9, 10).
Leider sind die realen Folgen nicht so 'gleichveteilt' wie diese Beispielfolge. Man kann also nicht einfach in der Mitte halbieren etc.
Eine reale Folge könnte beispielsweise so aussehen:
1,2,4,4,5,5,5,7,8,8,9,10,10,10
Wie kann ich die bestmöglichen Grenzen errechnen?
Danke euch!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:20 So 27.07.2008 | | Autor: | ullim |
Hi,
wenn Du die Gesamtanzahl der aufzuteilenden Elemente durch die Anzahl der Gruppen teilst und dann sukzessive in aufsteigender Reihenfolge die Element den Gruppen zuordnest.
Für Dein Beispiel 1,2,4,4,5,5,5,7,8,8,9,10,10,10 ergibt sich für 3 Gruppen
14/3 = 4 Rest 2 also
1 Gruppe mit 4 Elementen und 2 Gruppen mit 5 Elementen. Dir Grenzen sind entweder (4, 8,10) oder (5, 8,10)
mfg ulim
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:27 So 27.07.2008 | | Autor: | hoare |
Hi Ulli,
erstmal danke für deine Antwort. Leider hilft sie mir nicht wirklich weiter, denn sie lässt die Anzahl der einzelnen Elemente außer acht. Vielleicht bist du aber auch davon ausgegangen, dass ich einzelene Elemente auf verschiedene Gruppen aufteilen kann, was nicht möglich ist. Eine Gruppe mit lauter Einsen und Zweien besteht am Ende eben genau aus allen vorhandenen Einsen und Zweien. Eine Gruppe mit Dreien aus genau allen Dreien etc.
Hier mal eine Folge, bei der die einfache Einteilung in 3 Segmente nicht wirklich gut funktioniert:
1, 2, 2, 5', 5, 5, 5, 5,' 6, 9, 10, 10'
demnach enthalten zwei Gruppen eine Fünf, was eben nicht möglich ist. Eine sinvolle Einteilung für meine Zwecke wäre für diesen Fall
Gruppe A mit 1en und 2en
Gruppe B mit 5en
Gruppe C mit 6en 9en 10en
Existiert ein mathematisches Verfahren für so etwas, das mir die Grenzen durch eine Rechnung etc. liefert oder muss ich tatsächlich algorithmisch vorgehen?
Dankeschön!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:17 Mo 28.07.2008 | | Autor: | M.Rex |
Hallo
Ich vermute, dass du hier tatsächlich keine allgemeine Lösung bekommst.
Ich würde versuchen, erstmal gleiche Folgenglieder zusammenzufassen zu einer neuen Folge. also in deinem Beispiel:
[mm] \underbrace{1}_{a_{1}},\underbrace{2,2}_{a_{2}},\underbrace{5,5,5,5,5}_{a_{3}},\underbrace{6}_{a_{4}},\underbrace{9}_{a_{5}}, \underbrace{10,10}_{a_{6}}
[/mm]
Und jetzt hast du ja eine Folge, bei der du erstmal beliebig die Trennstriche setzen kannst.
Wenn du jetzt noch die Anzahl der Elemente der [mm] a_{i} [/mm] dazunimmst, kannst du die Anordnung der Trenner optimieren.
Dazu führe mal die Gewichtigkeit, also die Anzahl der Elemente der Einzelgruppen ein.
Also hier:
[mm] a_{1} [/mm] hat die Gewichtigkeit 1, a{2} die Gewichtigkeit 2, [mm] a_{3} [/mm] die Gewichtigkeit 5....
Berechne jetzt auch mal die "mittlere Gewichtigkeit" [mm] \mu [/mm] der Gruppen die du ja durch die Anzahl n der Daten und die Anzahl k der gewünschten Gruppen errechnen kannst: [mm] \mu=\bruch{n}{k}
[/mm]
Also hier: [mm] \mu=\bruch{12}{3}=4
[/mm]
Und jetzt solltest du Gruppen "herzaubern", deren Gewichtigkeit nicht allzustark von der 4 abweicht.
[mm] \underbrace{\underbrace{1}_{a_{1}},\underbrace{2,2}_{a_{2}}}_{\text{Gewichtigkeit 3 (1)}},\underbrace{\underbrace{5,5,5,5,5}_{a_{3}}}_{\text{Gewichtigkeit 5 (1)}},\underbrace{\underbrace{6}_{a_{4}},\underbrace{9}_{a_{5}}, \underbrace{10,10}_{a_{6}}}_{\text{Gewichtigkeit 4 (0)}}
[/mm]
In Klammern jeweils die Abweichung zu [mm] \mu
[/mm]
Mit der Methode der kleinsten quadratischen Abstände kannst du jetzt die Gesamtabweichung dieser Aufteilung ermitteln, und damit dann die mit der kleinsten Abweichung als Bestmögliche bestimmen.
Marius
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:26 Mo 28.07.2008 | | Autor: | hoare |
Hi Marius,
danke dir für deinen Vorschlag. Ich denke mittlerweile auch, dass es sich hier möglicherweise um ein NP-Schweres algorithmisches Problem handelt und werde es mal drüben im Informatikforum probieren.
Danke allen, die sich an der Lösung versucht haben!
hoare
|
|
|
|
