Zufallsreihen

[gnasen]

Ich habe keine vergleichbare Funktion in der Suche gefunden, deswegen dachte ich, ich teile sie einfach mal.

Code: Alles auswählen

Procedure.s zufallsreihe(anzahl)
  
  Protected reihenfolge.s = ""
  Protected Dim mischen_array(anzahl-1)
  
  For i = 0 To anzahl-1
    mischen_array(i)=1
  Next
  
  For i = 1 To anzahl
    zufall.l = Random(anzahl-i) + 1
    a.l=0
    While zufall > 0
      If mischen_array(a)=1
        zufall - 1
      EndIf
      If zufall > 0
        a + 1
      EndIf
    Wend
    mischen_array(a)=0
    reihenfolge = reihenfolge+Str(a+1)+";"
  Next
  ProcedureReturn reihenfolge
  
EndProcedure

Es geht darum, einfache Zufallsreihen zu bilden. Zum Beispiel eine Zufallsreihe aus 5 Zahlen wäre:

3;1;2;5;4; oder 2;5;3;4;1;

Diese wird als String zurückgegeben und kann mittels Stringfield bequem ausgelesen werden.

Geschwindigkeit ist denk ich mal akzeptabel:
100 x eine 10er Reihe: 0ms
100 x eine 100er Reihe: 16ms
100 x eine 1000er Reihe: 875ms

Wie ich das Forum kenne, wird sehr schnell eine effektivere Methode gepostet, aber immer her damit, haben alle was von

[AND51]

Würde mich gern dransetzen, aber ich verstehe nicht, worauf du hinaus willst...
Angenommen ich gebe der Prozedur die Zahl 7. Soll die dann 7 Zufallszahlen von 1-7 zurückgeben?
Also immer n Zufallszahlen von 1 bis n, wobei n > 0?
Ich mach das einfach mal...

Zu den Mitmachregeln: Muss die Zahlenreihe unbedingt als String zurückgeben? Oder darf's auch gleich eine LinkedList oder ein Array sein, das man zurückgibt? Du musst wissen, Zahlen in Strings umzuwandeln und umgekehrt ist eine ziemlich langsame Angelegenheit!

// Edit:
Ah jetzt verstehe ich:
Jede Zahl darf dabei nur einmal vorkommen! Wenn ich also 4 übergebe, dann dürfen nur Zufallszahlen von 1-4 dabei rauskommen, und dabei jede Zahl nur 1 Mal... Richtig?

[#NULL]

es geht wahrscheinlich darum, dass die reihe jede zahl zwischen 0 und n genau einmal enthält (keine dubletten und keine zahl auslassen).

[NicTheQuick]

Ich würde es z.B. so machen:

Code: Alles auswählen

Procedure zufallsreihe2(anzahl.l, List.l())
  anzahl - 1
  Protected Dim mixed.l(anzahl), i.l
  
  For i = 0 To anzahl
    mixed(i) = i
  Next
  For i = 0 To anzahl
    j = Random(anzahl)
    Swap mixed(i), mixed(j)
  Next
  For i = 0 To anzahl
    AddElement(List())
    List() = mixed(i) + 1
  Next
EndProcedure

NewList reihe.l()
RandomSeed(ElapsedMilliseconds())

zufallsreihe2(10, reihe())
ForEach reihe()
  Debug reihe()
Next

///Edit:
So gehts übrigens auch:

Code: Alles auswählen

Procedure zufallsreihe2(anzahl.l, List.l())
  anzahl - 1
  Protected Dim mixed.l(anzahl), i.l, j.l, k.l
  
  For i = 0 To anzahl
    k = Random(anzahl)
    If Not mixed(k) : mixed(k) = k + 1: EndIf
    If Not mixed(i) : mixed(i) = i + 1: EndIf
    Swap mixed(i), mixed(k)
  Next
  For i = 0 To anzahl
    AddElement(List())
    List() = mixed(i)
  Next

[AND51]

Ich würde es z.B. so machen:

Code: Alles auswählen

Procedure.s myZufallsreihe(zahl, Separator$=";")
	Protected Dim reihe.l(zahl), n, result.s
	reihe(0)=zahl
	Repeat
		reihe(zahl)=zahl
		zahl-1
	Until Not zahl
	For n=1 To reihe(0)
		Swap reihe(n), reihe(Random(reihe(0)-1)+1)
	Next
	For n=1 To reihe(0)
		result+Str(reihe(n))+Separator$
	Next
	ProcedureReturn result
EndProcedure

Debug myZufallsreihe(5)

@ gansen:
Bei mir kannste dir deinen Separator aussuchen, schließlich willst du das ja auch mit StringField() später auseinandernehmen.

@ NtQ:
Du hast vergessen, 'j' zu protecten und außerdem ist diese Variable überhaupt unnötig.

@ Mich selber:
Schneller posten...

[gnasen]

Uh yeah, so dachte ich mir das schon, muss mir eure Lösungen mal genauer anschauen, aber so meinte ich es!

Vielleicht könnte man auch noch die Startzahl angeben, so als kleine Idee. Übergabe in LL oder Array geht natürlich auch, ich fands mit dem String einfach bequem

[Kaeru Gaman]

eure codes blick ich ausm stehgreif nich... vielleicht hab ich die aufgabenstellung mistverstanden...

ich würds so machen:

Code: Alles auswählen

Procedure.s Reihe( Anzahl )

  If Anzahl > 9
    ProcedureReturn "ERROR"
  EndIf

  Dim Merker.l(8)
  Out$ = ""
  
  For n=1 To Anzahl

    Repeat
      Zufall = Random(Anzahl)
    Until Merker(Zufall) = 0
    Merker(Zufall) = 1
    Out$ + Chr(49+Zufall)

  Next
  
  ProcedureReturn Out$
EndProcedure

For n=0 To 12
  Debug Reihe(7)
Next

meine Routine braucht zwar aufgrund das trial&error-prinzips wesentlich mehr erzeuger-durchläufe,
aber dafür ist der einzelne durchlauf schneller, die routine schlanker, robuster, einfacher.

[AND51]

Das stimmt (zumindest) nicht (ganz).
Es gibt keine einfacherere und schnellere Methode, als die, die NtQ und ich gewählt haben.

Das Prinzip ist folgendes: Ein Array (oder LL) mit X Elementen anlegen, und füllen (1. Element = 1, 2. Element = 2, ...),
dann jedes Element mit For durchgehen und mit einem anderen zufällig ausgewählten Element vertauschen.

Dein Prinzip dagegen (siehe deine innere Repeat-Schleife), erzeugt solange eine Zufallszahl, bis eine erwischt wird, die es noch nicht gibt. Dadurch kommen in jedem Fall mehrere Schleifendurchläufe zusammen:
Wenn x=8 ist und die letzte Zahl gesucht wird, dann beträgt die Wahrscheinlichkeit 1 zu 8 (also gerade mal 12,5%), dass eine "freie" Zahl erwischt wird.

// Edit:
@ Kaeru:
Und schooon gibt's bei dir einen IMA, wenn Anzahl=9 ist, weil dein Array nur 8 Elemente hat; Random() könnte aber auch mal 9 als Zufallszahl auswerfen, passierte mir gerade beim 1. Durchlauf beim Speedtest.

// Edit 2:
OK, das mit der Performance muss ich grad noch überdenken, möglicherweise stimmt das doch nicht so ganz. Deine Prozedur schneidet merkwürdigerweise sehr viel besser ab, beim Speedtest, dennoch habe ich Recht, was die Anzahl deiner Schleifendurchläufe betrifft; im ungünstigsten Fall stimmt das also mit den 12,5% (wenn das Beispiel Anzahl=8 zugrunde liegt und die letzte Zahl untergebracht werden muss).

Außerdem bemerke ich grad, du hast vergessen, einen Separator einzufügen? Und was ich schon vorher merkwürdig fand: Wieso limitierst du Anzahl auf 9?

[gnasen]

Ich denke, dass die Routine von Kaeru bei kleinen Reihen sehr viel schneller sein kann. Bei großen Reihen jedoch müsste die Geschwindigkeit wesentlich schneller abnehmen, als die von den anderen Prozeduren, da die Wahrscheinlichkeit, einen schon besetzten "Platz" zu erwischen stark zunimmt.

[AND51]

Stimmt. Deshalb war seine so schnell.

Habe hier noch eine, aber ihr müsst mir mal helfen: Führe ich die Prozedur allein aus, zum Testen, klappt alles wunderbar.
Packe ich sie jedoch mit den anderen Prozeduren Prozeduren für einen Speedtest zusammen, hängt meine Peozdur bei der Repeat-Schleife fest? Warum?

Außerdem verstehe ich nicht, warum die ForEach()-Schleife nicht genauso oft durchlaufen wird, wie die Anzahl.

Das Prinzip ist folgendes:
Zuerst wird die LinkedList mit aufsteigenden Zahlen befüllt.
Danach gehe ich alle Elemente von vorn bis hinten mit ForEach() durch. Dabei merke ich mir das aktuelle Element (mit Hlfe seines Pointers). Ich vertausche 2 Elemente an sich (nicht die Zahlen, also den Inhalt!) und stelle danach das aktuelle Element wieder her (ChangeCurrentElement()).
Eigentlich müsste ForEach doch da weiterblättern, wo es aufgehört hat?

Tut es aber nicht! Wenn ich 8 angebe, müsste die ForEach-Schleife auch 8x durchlaufen werden, oft wird sie aber weniger durchlaufen (jedoch nie öfter als 8x).

Warum ist das so?

Code: Alles auswählen

Procedure myZufallsreihe2(zahl, LinkedList.l())
	Repeat
		AddElement(LinkedList())
			LinkedList()=CountList(LinkedList())
	Until CountList(LinkedList()) = zahl
	ForEach LinkedList()
		Protected *element=@LinkedList()
		SelectElement(LinkedList(), Random(zahl-1))
		SwapElements(LinkedList(), *element, @LinkedList())
		ChangeCurrentElement(LinkedList(), *element)
	Next
EndProcedure

NewList test.l()
myZufallsreihe2(8, test())
ForEach test()
	Debug test()
Next