zufallszahl aus einem int-array ohne wiederholung

CdWechsler · 11. April 2013

Guten morgen,

ich stehe etwas auf dem Schlauch, um eine Zufällige Zahl aus einem int[5] array ohne wiederholung zu generieren. Bei nur 5 Zahlen kommt es schon oft vor, dass die gleichen Zahlen hintereinander gewählt werden. Dann dachte ich mir die generierte zahl zwischen zu speichern um bei der nächsten generierung diese mit der neu generierten Zahl zu vergleichen. Falls diese dann gleich sein sollten, sollte dann so lange eine zahl generiert werden, bis diese sich mit der zwischen gespeicherten unterscheidet. Aber das würde eventuell auch länger dauertn, weil wie gesagt, kam es schon vor, das die gleiche zahl 4-5 mal hintereinander gewählt wurde. Das wäre also keine optimale lösung. Hat jmd. da vielleicht einen Tip??
So weit bin ich momentan:

Code

Random r = new Random();
int i;
int [] arrayList   = {13,32,44,33,99};
i = arrayList[r.nextInt(arrayList.length)];

danke im Voraus

hobride · 11. April 2013

Was hältst Du davon das Array nach jedem Durchlauf um eins zu verkleinern bzw. das gezogene Feld zu entfernen?

Marco Feltmann · 11. April 2013

Nun ja, zufällige Zahlen bedeuten eben auch, dass zufälligerweise dieselbe Zahl 5x hintereinander kommt.
Gerade beim Rollenspiel (so mit Würfeln) ist man sehr scharf drauf, dass eben genau das passiert: der Zufall soll die günstigsten Zahlen ausspucken.

Ich vermute, dass du eigentlich gar keine Zufallszahl möchtest.

Eigentlich ist das ganz simpel: Du möchtest, dass ein Objekt nur ein einziges mal gezogen wird. Wo haben wir das noch?
Genau, beim Lotto. 6 aus 49 oder so.

Wie sorgen die dafür, dass nicht drei mal hintereinander die 3 gezogen wird?
Die 3 fliegt aus dem Pool, sobald sie gezogen wurde.

Dazu könnte man also sagen:

Java

Random r = new Random();
int i;
List&lt;Song&gt; allItems   = ...;
List&lt;Song&gt; itemsCopy = new List&lt;Song&gt;();
// Hier deine Random-Methode:
private Song randomSong()
{
  if(itemsCopy.getSize() == 0)
  {
    itemsCopy = allItems;
  }
  Song randomSong = itemsCopy.get(r.nextInt(itemsCopy.getSize));
  itemsCopy.remove(randomSong);
  return randomSong;
}

Alles anzeigen

Wenn deine Objektkopien leer sind, dann nimmst du einfach die Objekte da rein.
Nun wird zufällig ein Objekt gewählt und aus den Objektkopien geworfen. Damit schrumpft die Größe um 1.
Wenn also eben r=3 war und jetzt wieder r=3 ist, gibt es dennoch ein anderes Objekt.

Irgendwann ist die Größe == 0. Und dann wird die Objektkopie erneut gesetzt.

Noch feiner wäre es natürlich, ganz auf diesen Random-Kram zu verzichten, eine gemischte Liste zu erstellen und einfach immer das erste Objekt zurückzugeben.

Java

List&lt;Song&gt; allItems   = ...;
List&lt;Song&gt; itemsCopy = new List&lt;Song&gt;();
// Hier deine Random-Methode:
private Song randomSong()
{
  if(itemsCopy.getSize() == 0)
  {
    itemsCopy = allItems;
    Collections.shuffle(itemsCopy, new Random(System.nanoTime()));
  }
  Song randomSong = itemsCopy.get(0);
  itemsCopy.remove(randomSong);
  return randomSong;
}

Alles anzeigen

block_ · 11. April 2013

Kleine Anmerkung zum Beitrag von Lucas:

Code

itemsCopy = allItems;

Da wird die Referenz von allItems an itemsCopy zugewiesen. Somit zeigen beide auf die selbe (original) Liste.

So wird eine (flache) Kopie erstellt.

Code

List&lt;Song&gt; allItems   = ...;
[..]
List&lt;Song&gt; itemsCopy = new ArrayList&lt;Song&gt;(allItems);

Ansonsten stimme ich Lucas voll und ganz zu.

block_

Marco Feltmann · 11. April 2013

Soviel zum Thema 'In Java gibt es keine Zeiger'...
Danke für die Anmerkung.

UweApps · 11. April 2013

Du kannst auch die ArrayList mischen mit Collection.shuffle(allItems) - wenn du es einfach haben willst.

@Lucas:
In Java ist fast alles ein Zeiger - außer den Basis-Typen. Darum braucht man nicht extra davon zu reden, das spart viel Verwirrung beim Erklären von Java... *g*

Marco Feltmann · 12. April 2013

Zitat von UweApps

Du kannst auch die ArrayList mischen mit Collection.shuffle(allItems) - wenn du es einfach haben willst.

Random Krams ohne Random Seed sind erfahrungsgemäß nur halb so random.
Die Variante mit System.nanoTime() als Seed finde ich zufälliger.

Zitat von UweApps

In Java ist fast alles ein Zeiger - außer den Basis-Typen. Darum braucht man nicht extra davon zu reden, das spart viel Verwirrung beim Erklären von Java... *g*

Bei Zeigern auf Zeiger oder Zeiger auf Methoden versagen sie dann. Nicht sehr konsequent, wenn du mich fragst.

CdWechsler · 12. April 2013

Hallo an alle und danke für die posts,

also was ich am code von lucas nicht verstanden habe ist "Song".

wenn ich das so übernehme steht beim List<Song>: Song cannot be resolved to a type
keine ahnung wie ich das fixe (sry, aber ich muss noch einiges lernen ), aber egal, den prinzip habe ich verstanden. wobei wenn das letzte element von itemscopy beispielsweise eine 5 wäre, welches dann gelöscht wird dann wäre itemscopy = 0. somit wäre die if-bedingung erfüllt und itemscopy bekommt alle elemente von allitems zugewiesen, welches dann zufällig gemischt wird. dann wird wieder das 1. element genommen, welches aber auch die 5 sein kann. d.h. es wäre dann 2 mal hintereinander gezogen worden. naja... wenn das alle 5 schritte passieren kann ist das nicht so tragisch. aber zurück zum code: wie gesagt, ich habe das mit der methode Song nicht so verstanden und habe das dann so gemacht um zu checken, ob keine gleichen zahlen hintereinander aufgelistet werden:

Code

List&lt;Integer&gt; list = new ArrayList&lt;Integer&gt;();
		
		list.add(1);
		list.add(2);
		list.add(3);
		list.add(4);
		list.add(5);
		
		List&lt;Integer&gt; list2 = new ArrayList&lt;Integer&gt;(list);
				
		Random r = new Random(System.nanoTime());


		int i = 0;


		while(i != 16) {
			if(list2.size() == 0) {
			list2 = list;
			Collections.shuffle(list2, r);
		}
		
		int b = list2.get(0);
		System.out.println(b);
		list2.remove(b);
		i++;
		}

Alles anzeigen

so, normalerweise sollte es mir 16 zahlen zurückgeben. was ich bekomme ist aber seltsamerweise das hier:

Code

1
1
1
1
1
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 1, Size: 1
	at java.util.ArrayList.rangeCheck(Unknown Source)
	at java.util.ArrayList.remove(Unknown Source)
	at Main.main(Main.java:32)

NACHTRAG:

upss, habe die klammer falsch gesetzt (peinlich peinlich)

ThomasDroid · 12. April 2013

Mit i definierst du wie oft er die while-Schleife durchlaufen soll. Sprich wie oft du eine Zahl dir raussuchst und sie später auch entfernst.
Dieser Wert ist bei dir 16.

Du fügst am Anfang aber nur 5 Elemente in die Liste ein. {1,2,3,4,5}
Dadurch wird beim 6. Schleifendurchlauf auf eine leere Liste zugegriffen.

Entweder musst du i auf 5 setzen. Oder 16 Werte in die Liste einfügen.

CdWechsler · 12. April 2013

Hallo ThomasDroid,

ja, ich hatte die Klammer falsch gesetzt (siehe Nachtrag)

Danke

ThomasDroid · 12. April 2013

Das erklärt natürlich einiges.

Ich würde übersichtshalber anstatt der while / if Konstruktion eine for schleife nehmen.
Du kannst einfach schreiben

Java

for(int i = 0; !list2.isEmpty; i++){//code}

dieses !list2.isEmpty überprüft ob noch ein Element in der Liste vorhanden ist. Das i zählt dann einfach hoch, bis das letze Element gelöscht wurde. Dadurch musst du keine Zahl hart codieren.

CdWechsler · 12. April 2013

Nachtrag

Thomas:
ich wollte ja auch, das sobald list2 leer ist, diese wieder gefüllt wird. Insgesamt sollte das 3 mal passieren, daher habe ich auch 16 eingetragen. also 16 zufällige zahlen von list2.get(0);

Zitat

Dadurch wird beim 6. Schleifendurchlauf auf eine leere Liste zugegriffen.

dann soll die if-bedingung doch ausgeführt und die list2 wieder gefüllt werden. Warum bekomme ich trotzdem 5 mal die 1 ausgespuckt?? (nebenbei mal gefragt)

ThomasDroid · 12. April 2013

1. die Collections.shuffle(list2, r); wird erst aufgerufen, wenn du das zweite mal das Array wieder kopierst.
-> du solltest nach dem

Java

List&lt;Integer&gt; list2 = new ArrayList&lt;Integer&gt;(list);		Random r = new Random(System.nanoTime());

diese Funktion einmal aufrufen, dass auch beim ersten Durchlauf dieser 5 Zahlen das Array durcheinander ist.

2. Schau mal in der Java API unter ArrayList, was die Funktion remove(int index) macht. Diese wird nämlich aufgerufen. Obwohl du wahrscheinlich an die Methode remove(Object o) gedacht hast. Das ist wichtig das zu verstehen (!!)

-> was du wolltest wäre z.B.

Java

int b = list2.remove(0);

diese Funktion entfernt das 0te Objekt und gibt das Element zurück. In dem Falls wird es dann in die Variable b gespeichert.

ThomasDroid · 12. April 2013

Ein weiterer Fehler ist in der Zeile mit

Java

list2 = list;

Dort werden nicht die werte von der list in list2 kopiert, sondern list2 verweist jetzt auf list.

folgendes passiert:

1. Durchlauf: Alles funktioniert, da mit List<Integer> list2 = new ArrayList<Integer>(list); die Werte von list in die list2 kopiert wurden.

2. Durchlauf: funktioniert auch noch, da list2 jetzt auf list verweist. ABER die Elemente aus der list werden jetzt auch entfernt.

3. Durchlauf: Crashed, da keine Werte mehr in list vorhanden sind.

Anstatt list2 = list; musst du mit einer Schleife das Array list durchlaufen und jedes Element der list2 hinzufügen. Mit den Funktionen und nicht mit dem = Operator!

CdWechsler · 12. April 2013

Thomas,

jep, genau das waren die macken. immer diese kleinen Flüchtigkeitsfehler.

Es ist genau so wie gelaufen, wie du es beschrieben hast. Nach dem 2. durchlauf (beim 3. füllen des list2) waren alle elemente weg und bekam wieder die indexoutofboundsexception. ich bin mir immer noch nicht im klaren bin, warum die elemente von list entfernt werden!?? danke das du mir das mitgeteilt hast, sonst hätte ich noch länger daran gesessen xD
ich habe daher in die if-bedingung folgendes eingefügt:
list2 = new ArrayList<Integer>(list);
list2 = list; habe ich natürlich entfernt. und es funzt

ThomasDroid · 12. April 2013

unnötige new sind nie gut. Da wird jedes mal neuer Speicher reserviert. Bei einem kleinen Programm ist das nicht schlimm, aber wenn sich das häuft, leidet die Performence.

mach es lieber so:

Java

for(int j = 0; j &lt; list.size(); j++){
	 list2.add(list.get(j));	
 }

CdWechsler · 12. April 2013

super, danke dir

Marco Feltmann · 12. April 2013

[CdWechsler]
Ich hatte zu deinen Fragen nix mehr geschrieben, weil all das eigentlich schon hier steht...
Das mit dem Song war ein aus dem Leben gegriffenes Beispiel, dass du da deine eigenen Datentypen rein packen kannst/sollst/darfst, habe ich als Grundlagenwissen vorausgesetzt...

[ThomasDroid]
Ich denke, der GarbageCollector ist so geil? Der müsste ja eigentlich mitbekommen, dass wenn ich list2 = new List(list) mache, die alte Referenz auf list2 weggeworfen gehört.

Im Beispiel mit New gibt es genau eine Nachricht an ein Klassenobjekt, welches dann genau X Byte an Speicher für sein Objekt zurückgibt.
Das Beispiel mit der Schleife ist zunächst einmal eine Schleife. Weiterhin gibt es list.size() Nachrichten an ein Instanzobjekt Liste2 und an ein Instanzobjekt Liste.
Im günstigsten Fall also die doppelte Menge an Nachrichten, Tendenz steigend.

Der erste Ansatz erfordert ein wenig mehr RAM, was dank des GarbageCollectors nur kurz auffallen dürfte. Der zweite Ansatz hingegen erfordert im Verhältnis Unmengen an Prozessorleistung. Hinzu kommt, dass eine Collection meines Wissens ihren Speicherbedarf dynamisch regelt. Eine Liste mit 0 Objekten braucht natürlich weniger Speicher.

Statt also 1x X Byte an Speicher zu reservieren legt die Schleife list.size() mal sizeOf(Integer) Byte zusätzlich an. Derartige Neuzuweisungen von Speicher sind ebenfalls prozessor- und sogar RAM intensiv.

Bevor man also ein new... durch eine Schleife ersetzt soll einem zunächst wirklich mal das RAM um die Ohren geflogen sein.
Garbage Collection wurde 1959 im Rahmen von Lisp eingeführt. In den fast 55 Jahren sollte man doch annehmen, dass sich das ganze System einigermaßen etabliert hat. Und auch wenn niemand weiß, wann genau GarbageCollection aufräumt, so räumt es doch auf, bevor RAM zur Neige geht.

Finger weg von vermeidlichen Optimierungen ohne vorherige Tests und definitiver Probleme.
POITROA.

ThomasDroid · 12. April 2013

Ich kenn mich mit Java auch nicht so gut aus.
Aber ich würde behaupten wenn man ein new macht und eine Liste übergibt, dass es die Werte übernhemen soll,
müssen die werte genauso kopiert werden wie mit einer Schleife und dabei muss auch die Größe bestimmt werden. Und dazu noch Speicher allokiert werden. Klar der Garbage kollektor macht viel, aber braucht auch seine rechenzeit dafür...

Ich kenn es auf jedenfall von c++, dass zuweisungen viel weniger Zeit brauchen als speicherallokation.

Aber ich kenn mich auch nicht so gut aus. Das gleiche Ergebnis kommt auf jedenfall raus

CdWechsler · 12. April 2013

jep, für mich zählt erstmal das ergebnis. beide varianten möglich

danke euch

zufallszahl aus einem int-array ohne wiederholung

Jetzt mitmachen!

Teilen