Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
DatentypenMehrere int Variablen miteinander vergleichen
Ich habe ein Problem mit ein paar Integer Variablen, und zwar habe ich 5 int Variablen, welchen ich jeweils ein zufallswert zuweise:
Java:
int z1 = rnd.nextInt(intervall);
int z2 = rnd.nextInt(intervall);
int z3 = rnd.nextInt(intervall);
int z4 = rnd.nextInt(intervall);
int z5 = rnd.nextInt(intervall);
wie bekomme ich es jetzt möglichst kurz hin, das die Variablen miteinander verglichen werden, sodass kein Variablenwert doppelt vorkommt ?
Wenn nicht, darfst du Arrays benutzen? Wenn ja, mach`s mit einem Array/Collection
Wenn ja, vllt kannst du ja mal mehr erzählen über die genaue Aufgabenstellung =)
Ne die aufgabe habe ich nicht, kann also Arrays benutzen
Eine genaue Aufgabenstellung habe ich allerdings auch nicht.
Allerdings möchte ich 5 Variablen einen Zufallswert zuweisen, welcher aber NICHT gleich sein darf.
Aber ich muss mit den Werten auch weiterhin rechnen können.
Dann würde Ich einfach ne ArrayList anlegen, diese kann ganz einfach gefragt werden, ob Sie einen bestimmten Wert schon enthält und die weiterverwendung der elemente is easy...
Man kann das "irgendwie" machen. Und das funktioniert dann. Aber wenn man ein bißchen (wirklich nur ein bißchen) theoretisch ausholt, ist das gar nicht so leicht.
Man hat - je nachdem, worum es genau geht - verschiedene Möglichkeiten:
- Man könnte so lange Elemente in eine Set einfügen, bis sie die benötigte Größe hat
- Man könnte alle Zahlen des Intervalls mischen, und sich 5 davon rauspicken.
Wenn man ersteres macht, dann sollte man wirklich ein Set verwenden, und keine ArrayList. Festzustellen, dass ein Element NICHT in einer List enthalten ist, ist relativ aufwändig.
Das Problem dabei ist in jedem Fall: Es terminiert nicht notwendigerweise. Wenn man das für deinen Fall schreiben würde, wäre das ja
Java:
int invervall = ...
Set<Integer> set = new HashSet<Integer>();
while (set.size() < 5)
{
set.add(rnd.nextInt(intervall));
}
Ganz trivial und straightforward. Und dann setzt man mal für "invervall" den Wert 4 ein, und schaut, wie weit man kommt OK, sowas kann (und sollte) man vorher abfragen, aber selbst wenn man ein Intervall von 100000 verwendet, ist nicht sichergestellt, dass das Programm irgendwann fertig ist.
Die zweite Lösung wäre sowas wie
Java:
int invervall = ...
List<Integer> list = new ArrayList<Integer>();
for (int i=0; i<intervall; i++)
{
list.add(i);
}
Collections.shuffle(list);
List<Integer> result = list.subList(0,5);
Auch ganz trivial und straightforward. Und dann setzt man mal für "invervall" den Wert 2000000000 ein, und schaut, wie weit man kommt Der "Vorteil" ist, dass dieses Verfahren garantiert terminiert.
Man könnte sagen, dass des vom Verhältnis zwischen Intervallgröße und Anzahl der Zahlen abhängt, welches Verfahren man wählen sollte. (Auch wenn das nicht-terminieren im ersten Fall eher ein theoretisches Problem ist, kann sowas bei einem Intervall von 1000000 und 999999 zu ziehenden Zahlen schon eine ganze Weile dauern...).
Wobei die Frage schon öfter aufgetaucht ist. Mal überlegen, ob man da nichteine Lösung finden kann, die garantiert terminiert, OHNE bei großen Intervallen astronomisch viel Speicher zu benötigen :reflect:
Wobei die Frage schon öfter aufgetaucht ist. Mal überlegen, ob man da nichteine Lösung finden kann, die garantiert terminiert, OHNE bei großen Intervallen astronomisch viel Speicher zu benötigen :reflect:
import java.util.*;
public class LinearRandomPick {
public static long mod(long n, long m){
return ((n%=m)<0)?n+m:n;
}
public static Long get(Long index, Map<Long,Long> replacements){
if(replacements.containsKey(index)){
return replacements.get(index);
}else{
return index;
}
}
public static List<Long> pick(int number, long intervalEnd){
HashMap<Long,Long> alreadyUsed=new HashMap<Long,Long>(); //O(1)
List<Long> result = new LinkedList<Long>(); //O(1)
Random r = new Random(); //O(1)
for(int i=0; i<number; i++){
long pickedIndex = mod(r.nextLong(),(intervalEnd-i)); //O(1)
long pickedNumber = get(pickedIndex, alreadyUsed); //O(1)
result.add(pickedNumber); //O(1)
alreadyUsed.put(pickedIndex,get(intervalEnd-1-i,alreadyUsed)); //O(1)
} //O(number)
return result;
}
public static void main(String..._){
System.out.println(pick(5,5));
System.out.println(pick(5,10));
System.out.println(pick(5,100));
System.out.println(pick(5,1000000000));
System.out.println(pick(5,Long.MAX_VALUE));
System.out.println(pick(2,2));
System.out.println(pick(10,10));
System.out.println(pick(100,100));
}
}
So ungefähr? Erwartet läufts linear in der Anzahl der zu wählenden Zahlen, der Speicherbedarf ist ebenfalls O(number), da bei jedem schleifendurchlauf einmal eingefügt wird.
Die Idee ist ähnlich wie beim linearen shuffle-Algorithmus auf einem Array, wo die einträge geswappt werden. Nur gibt es hier kein Array, sondern stattdessen die Menge aller Longs, und es wird nur virtuell geswappt, indem bereits gepickte Longs durch eine HashMap auf ihre "virtuellen swap-Partner" gemappt werden.
Von der Grundidee her wäre ich wohl ähnlich vorgegangen: Es mußte was sein, was indirekt auf der shuffle-Idee basiert, aber man sollte nicht den kompletten Array speichern müssen, sondern nur die Information, wo welche Zahl nach dem Shufflen gelandet wäre. Einerseits dachte ich: "Das kann ja nicht sooo schwer sein"... andererseits hätte ich nicht gedacht, dass das SO "einfach" ist - "einfach" aber im Sinne von: Wenig code. In bezug auf das, was man macht, ist das, was du da gebastelt hast, nämlich IMHO nicht "einfach", sondern schon ziemlich tricky - habe kurz versucht, es nachzuvollziehen, aber ... SO (kurz) hätte ich das wohl nicht hinbekommen :toll:
Ich bin aber auch immer ein bißchen vorsichtig mit Zufallszahlen, Wahrscheinlichkeiten und dem ganzen Kram - da kann man sich leicht auf die Fre... legen. In diesem Fall dachte ich beim ersten Durchlesen auch, dass durch das
[c]get(intervalEnd-1-i,alreadyUsed)[/c]
vielleicht größere Zahlen (am Ende des Intervalls) "bevorzugt" werden könnten, aber bei einem kurzen Histogrammartigen Test sah' es dann doch gleichverteilt aus ... Also: Wenn die Frage mal wieder auftaucht, weiß ich, auf welchen Beitrag ich verlinken kann :applaus:
Es gibt doch einen Algorithmus zur Bestimmung der x-ten lexiografischen Permutation von n Elementen (z.B. Permutations in C++, Part 2 - CodeGuru). x als Zufallszahl zwischen 0 und (n-1)! wählen, Algorithmus ausführen und gut - ohne irgendwelche Speicherplatzprobleme.
Hab den code dort jetzt nicht angesehen, aber ... wenn man damit auch ganz isoliert die k ersten Elemente der x-ten Permutation von n Elementen rausfinden kann, wäre das vielleicht auch eine Möglichkeit. Aber ob die dann noch kürzer ist, als die Lösung von Andrey...?
Hmmm, ich glaube, ich denke zu kompliziert. Für den Aufgabenfall reicht ja schon sowas:
Java:
public static Iterator<Integer> randomPickIterator(final int max){
return new Iterator<Integer>() {
private final Random random = new Random();
private final Set<Integer> set = new TreeSet<Integer>();
public boolean hasNext() { return set.size() < max; }
public Integer next() {
int r = random.nextInt(max - set.size());
for(Integer k : set) { if(r >= k) r++; }
set.add(r);
return r;
}
public void remove() { throw new UnsupportedOperationException(); }
};
}
Ich glaube ich denke zu kompliziert - oder resigniere zu schnell nach dem Aufstellen der Vermutung, es könnte kompliziert sein, und denke darum nicht darüber hinaus ... wie kommt ihr auf sowas? ;( Das scheint auch richtig zu sein ... und dabei ist egal, dass es O(n*k) statt O(n) hat - offenbar ist doch mal wieder jedes Problem so einfach, die die Lösung, die man clevererweise dafür findet...
Wie man auf sowas kommt kann ich in diesem Fall recht genau beantworten:
Mir war klar, dass man immer weniger Möglichkeiten hat und deshalb immer kleinere Zufallsbereiche braucht. In einen Zufallsbereich schieben sich aber nachträglich die schon gezogenen Zahlen "irgendwie dazwischen". Das Bild, das ich im Kopf hatte, war so eine Art unregelmäßige Ziehharmonika, wo sich die bereits gezogenen Zahlen im aktuellen Zufallsbereich "auffalten":
Ziehe Zufallszahl im um die Anzahl der schon gezogenen Zahlen verkleinertem Bereich:
----X----
Die schon vorhandenen Zahlen "falten" sich dazwischen auf:
--v-v-X-v---
Das ergibt die "echte" Position der neuen Zahl (zwischen den bereits vorhandenen):
--+-+-X-+---
Die praktische Umsetzung war dann einfach: Wenn ich Zahlen von 0 bis 9 haben will, und meinetwegen die fünf schon gezogen ist, brauche ich als nächstes nur noch eine Zufallszahl von 0 bis 8, muss diese aber eins nach oben verschieben, wenn ich eine 5 oder größer gezogen habe (das wäre die "Auffalt-Operation"). Die nächste Zufallszahl braucht dann nur noch von 0 bis 7, ich muss aber für die beiden vorangegangenen Zahlen wieder diese Verschiebung nach oben machen, und zwar nacheinander. Das "nacheinander" klappt nur, wenn diese aufsteigend geordnet sind, deshalb ein TreeSet.
Datenstrukturen und einfache Algorithmen sind für mich recht "plastisch", ich sehe die Operationen im Kopf ablaufen. Ich kann mir nicht vorstellen, wie man ohne diese Fähigkeit programmieren kann, aber inzwischen kenne ich genügend Leute, bei denen das nicht so (oder nicht so ausgeprägt) ist, und die trotzdem gute Programme schreiben, und kenne auch die Erklärungsansätze für diesen Unterschied (wie das Modell von Myers-Briggs, wo ich natürlich zu den "Intuitiven" zähle). Hin und wieder platze ich "spontan" mit einer richtigen Lösung heraus, und dann wissen meine Kollegen nicht, was sie davon halten sollen (ich fürchte irgendwann holen sie mal einen Exorzisten).
So betrachtet klingt das schon fast erschreckend einleuchtend ... Wenn ich versuchen sollte, das mir selbst gegenüber zu rechtfertigen, würde mir jetzt kaum was anderes einfallen als die Verblödung, die daraus resultiert, dass man die meiste Zeit des Tages nicht denken muss, sondern seine Zeit mit sinnlosem Office-Mist verschwendet.
Wenn ja, mach`s mit einem Array/Collection
