Gleichmäßig-Zufällige Array Verteilung

Rikudo · 22. April 2015, 14:52

Hey Community,

Ich stehe vor einem Problem bei dem ich nicht weiß wie ich es am besten umsetzen soll

Zuerst, was habe ich vor :
Ich möchte ein T[] in mehrere kleine arrays unterteilen (mit random größen) und dann ein T[][] zurückgeben, also
ein array welches die einzelnen kleineren arrays enthält.
Wichtig ist das die Arrays schön ihre Reihenfolge behalten.
Das konnte ich so umsetzen: (Dickes dankeschön an @~blaze~ )

C#-Quellcode

// Split an array into multiple multidemnsional arrays, with different, randomly choosen sizes
public static T[][] RandomSplitBlock<T>(T[] input)
{
if (input == null)
throw new ArgumentNullException("Input can't be null.");
Random rnd = new Random(DateTime.Now.Millisecond);
int index = 0;
List<T[]> ArrayBlocks = new List<T[]>();
while (index < input.Length)
{
int c = rnd.Next(1, input.Length - index);
T[] newArr = new T[c];
Array.Copy(input, index, newArr, 0, c);
ArrayBlocks.Add(newArr);
index += c;
}
return ArrayBlocks.ToArray();
}

Zum Problem.
Der obrige algorithmus funktioniert recht gut, was ich jedoch möchte ist eine etwas gleichmäßigere, trotzdem random(!) verteilung
der einzelnen arrayblöcke.

Bei 30 Array Items als input kommen often solche Ergebnisse :

z.B. unterteilt in 4 kleinere arrays, wobei:

array[0] = enthält 23 items
array[1] = enthält 2 items
array[2] = enthält 4 items
array[3] = enthält 1 items

Ich möchte jedoch das versucht wird etwas gleichmäßigere Verteilungen zu erreichen, z.B. sowas:

array[0] = enthält 7 items
array[1] = enthält 6 items
array[2] = enthält 8 items
array[3] = enthält 9 items

Also das nicht so enorme unterschiede wie z.B. 50 items und mal 2 items vorkommen, sondern halbwegs gleichmäßig.
Das muss nicht immer exakt sein, aber es soll versucht werden möglich gleichgroße arrays zu er-splitten.
Die Anzahl der zu erstellenden teil arrays soll nantürlich anch wie vor random gewählt werden, allerdings so, das
das mit der aufteilung halbwegs passt, 26 arrays bei 30 array items als input wäre halt blöd

Kann mir jemand helfen den Algorithmus so zu modifizieren das das oben beschrieben erreicht wird.
Ich weiß nicht recht wie ich das machen soll, - hoffentlich kann mir hier jemand von euch helfen

Lg
Rikudo

Rikudo · 22. April 2015, 18:57

Hat keiner eine Idee?

petaod · 22. April 2015, 19:04

Gib dem rnd.Next eine intelligente Obergrenze und Untergrenze mit.
Die muss ja nicht den ganzen Umfang erfassen, sondern kann auch +/- 10% um den Durchschnitt liegen.

RodFromGermany · 22. April 2015, 19:10

@petaod Jou.

Rikudo schrieb:

gleichmäßigere Verteilungen

Mach Dir im 1. Schritt eine Liste mit entsprechenden Anzahlen und befülle dann entsprechend dieser Liste Deine Arrays:

VB.NET-Quellcode

Private rnd As New Random
Private numbers As New List(Of Integer)
Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
For i As Integer = 0 To 9
numbers.Add(rnd.Next(5, 9))
Next
End Sub

Rikudo · 22. April 2015, 19:19

Das wird aber nicht leicht, denn mir sind ja die Grenzen nicht bekannt:

C#-Quellcode

int c = rnd.Next(1, input.Length - index);

Wenn ich eine Untergrenze von sagen wir ca 3 nehme, aber mein maximum ist nur 2, gibts probleme?
Kann ich nicht automaticsh irgendwie einen Wert wählen der etwas abweicht?

Artentus · 22. April 2015, 19:27

Du kannst z.B. zunächst anhand der Arraygröße ermitteln, wie viele kleinere Arrays du am Schluss ungefähr haben willst (dabei kannst du bereits eine zufällige Abweichung von einer dir sinnvoll erscheinenden Größe ansetzen). Dann berechnen, wie groß bei der ermittelten Anzahl ein Array sein müsste und bei jeder Iteration zu diesem Wert zufällig addieren und Subtrahieren (wobei du hier wiederum die Abweichung beliebig wählen kannst und vielleicht auch prozentual, also je größer die Teilarrays desto größer auch die mögliche Abweichung von dieser Länge).

Rikudo · 22. April 2015, 19:35

@Artentus :
Oje, jetzt hast du mich verwirrt..
Angenommen ich lege fest dass es sinnvoll ist jedem Teil-Array ca die Anzahl an Items zuzuweisen, die der Wurzel des Inputs entsprechen, mit einer Abweichung von +-2.
Wie würde dann die Zuweisung von

Quellcode

int c

aussehen?

Mokki · 22. April 2015, 20:10

Genau das was @RodFromGermany geschrieben hat.

C#-Quellcode

int c = rnd.Next(untere Grenze, obere Grenze);

Also hast du z.B. einen Array mit einer Länge von 40.
Nun fehlt die Anzahl der Array die du als Output haben möchtest, nehmen wir 4. Dann berechnest du die durchschnittliche Größe des einzelnen Array mit 40 / 4 = 10. Als Abweichung der Arrays voneinander nehmen wir 10% der Länge des ursprünglichen Array also 40 / 10 = 4. Nun noch die 4 / 2 = 2 (5% über dem Mittelwert, 5% darunter) und dann hat man die untere Grenze mit Mittelwert - 2 und die obere mit Mittelwert + 2.

Rikudo · 22. April 2015, 20:16

@Mokki :
Aber die Anzahl der Output array ist ja nicht imemr 4 sondern auch random.
Ich habs so versucht :

C#-Quellcode

int c = rnd.Next((int)Math.Sqrt(input.Length), input.Length - index);

Aber dann passiert genau das minvalue > maxvalue -> Crash

Mokki · 22. April 2015, 20:20

Ok dann schreib den Wert wie viele Arrays es gibt auch in ne Variable, also mit:

C#-Quellcode

int howmucharrays = rnd.next(1,input.Length);

Rikudo · 22. April 2015, 20:23

@Mokki :
Genau das ist ja das Problem

Deswegen weiß ich nicht wie ich

C#-Quellcode

int c =...

auscwählen soll, das im Startpost genannte Bedingungen zutreffen..

Mokki · 22. April 2015, 20:25

Welches Problem?

petaod · 22. April 2015, 20:29

Setze die Grenzen so: rnd.Next(Min(BerechneterUntererWert,ObererWert),ObererWert)

Rikudo · 22. April 2015, 20:32

petaod schrieb:

Setze die Grenzen so: rnd.Next(Min(BerechneterUntererWert,ObererWert),ObererWert)

ObererWert wäre ja dann :

C#-Quellcode

input.Length - index

, oder?
Aber was wäre UntererWert?

Ich verstehs einfach nicht wie sich der zusammensetzen soll

Mokki · 22. April 2015, 20:36

So:

C#-Quellcode

int c = rnd.Next(Input.Lenght / rnd.next(1,input.Lenght) - Input.Lenght / 10, Input.Lenght / rnd.next(1,input.Lenght) + Input.Lenght / 10);

Falls eine Abweichung von max. 10% bestehen soll.

Rikudo · 22. April 2015, 20:41

Mokki schrieb:

So:

C#-Quellcode

int c = rnd.Next(Input.Lenght / rnd.next(1,input.Lenght) - Input.Lenght / 10, Input.Lenght / rnd.next(1,input.Lenght) + Input.Lenght / 10);

Falls eine Abweichung von max. 10% bestehen soll.

Danke für deine Hilfe, aber das scheint nicht richtig zu funktionieren

(Input größe des Arrays waren 29 items)

ThePlexian · 22. April 2015, 20:50

Wenn du nichtmal angeben willst, wie viele Teilarrays rauskommen sollen, würde ich das so machen.
Zur Veranschaulichung hat unser Array mal 30 Items.
1. Eine Zufallszahl wählen, die etwa die Größe eines Teilarrays vorgibt. Ich würde vllt int size = rnd.Next(30 * 0.1, 30 * 0.4); vorschlagen.
2. Dann wie gehabt fortsetzen, aber für die Arraygröße jetzt folgende Grenzen wählen : int c = rnd.Next(size - (size * 0.5), size + (size * 0.5));

Dann wird bei größeren Arrays auch die Varianz größer.

Rikudo · 22. April 2015, 21:05

ThePlexian schrieb:

Wenn du nichtmal angeben willst, wie viele Teilarrays rauskommen sollen, würde ich das so machen.
Zur Veranschaulichung hat unser Array mal 30 Items.
1. Eine Zufallszahl wählen, die etwa die Größe eines Teilarrays vorgibt. Ich würde vllt int size = rnd.Next(30 * 0.1, 30 * 0.4); vorschlagen.
2. Dann wie gehabt fortsetzen, aber für die Arraygröße jetzt folgende Grenzen wählen : int c = rnd.Next(size - (size * 0.5), size + (size * 0.5));

Dann wird bei größeren Arrays auch die Varianz größer.

Danke für deine Antowort, ThePlexian

Allerdigns kommt da der gleiche Fehler wie bei Mokki's Vorschlag :

C#-Quellcode

public static T[][] RandomSplitBlock<T>(T[] Input)
{
if (Input == null)
throw new ArgumentNullException("Input can't be null.");
Random rnd = new Random(DateTime.Now.Millisecond);
int index = 0;
List<T[]> ArrayBlocks = new List<T[]>();
while (index < Input.Length)
{
int size = rnd.Next((int)(Input.Length * 0.1), (int)(Input.Length * 0.4));
int c = rnd.Next((int)(size - (size * 0.5)), (int)(size + (size * 0.5)));
T[] newArr = new T[c];
Array.Copy(Input, index, newArr, 0, c);
ArrayBlocks.Add(newArr);
index += c;
}
return ArrayBlocks.ToArray();
}

Probier das mal aus, da kommt der gleiche Fehler raus wie in dem Screenshot oben.
Irgendwas scheint nicht zu stimmen mit den Grenzen..

petaod · 22. April 2015, 21:16

Rikudo schrieb:

was wäre UntererWert

Bei deinem genannten eigenen Vorschlag die Wurzel aus Input.Length.
Ich wollte nur darauf hinweisen, dass du den Überlauf-Fehler mit Min abfangen kannst.

Welchen Verteilalgorithmus du letztendlich wählst, bleibt dir und deinen Tests überlassen.
Da führen viele Wege nach Rom.

Rikudo · 22. April 2015, 21:21

@petaod :
Das geht leider auch nicht, wie ich bereits in Post#9 geschrieben habe, dann wäre maxvalue kleienr als MinValue..

Gleichmäßig-Zufällige Array Verteilung

Gleichmäßig-Zufällige Array Verteilung

C#-Quellcode

Rikudo schrieb:

VB.NET-Quellcode

C#-Quellcode

Quellcode

C#-Quellcode

C#-Quellcode

C#-Quellcode

C#-Quellcode

petaod schrieb:

C#-Quellcode

C#-Quellcode

Mokki schrieb:

C#-Quellcode

ThePlexian schrieb:

C#-Quellcode

Rikudo schrieb:

Tags

Ähnliche Themen

6 Benutzer haben hier geschrieben