| 

.NET C# Java Javascript Exception

1
Mit der Methode shuffle der Klasse Collections kann ich Objekte (z.B. LinkedList- oder ArrayList-Objekte) durcheinander bringen, so dass diese in ungeordneter Reihenfolge vorliegen. Dazu wird intern ein Zufallsgenerator genutzt. Wie kann ich die Änderungen der Methode shuffle am einfachsten wieder rückgängig machen?
News:
26.06.2012
2 Antworten
1
Ich kenne jetzt Java nicht, aber wenn man in PHP z.B. einmal das Shuffle ausgeführt hat, gibt es keinen "Rückverweis" oder so. Die alten Indexpositionen werden da nicht gespeichert.

Wie groß sind denn Deine Collections? Wenn das Objekt nicht zu groß ist, würde ein einfach eine Kopie erzeugen und die Shuffeln. Wenn Du zurück musst, nimmst Du wieder die originale Collection. KISS ;)
26.06.2012
Xantiva 2,3k 1 9
0
Die von Xantiva genannte Option, eine der Kopie zu erstellen, wäre die nächstliegende. Selbst bei einer "großen" Liste gibt es dazu nur wenige Alternativen: Die Information, die man bräuchte, um das Collections#shuffle rückgängig zu machen wäre genauso groß wie die Liste selbst - nämlich irgendeine geeignete Abbildung der Elemente auf ihre alten Positionen.

Eine Option sollte man aber noch in Betracht ziehen - insbesondere bei großen Listen, und wenn Speicherplatz ein Problem sein könnte: Falls die "Zufälligkeit" des shuffle keinen kryptographischen Anforderungen genügen muss, kann man sich seinen eigenen Pseudo-Zufallszahlengenerator schreiben, mit dem man für einen übergebenen Index eine "zufällige" Zahl berechnet. Damit kann man eine Liste durch "zufällige" Vertauschungen shufflen, und diese bei Bedarf rückgängig machen, indem man die Vertauschungen einfach in umgekehrter Reihenfolge wieder anwendet. Gespeichert werden muss dafür dann effektiv nur ein random seed.

Ein KSKB, nur um die Idee zu verdeutlichen:
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

class UndoableShuffle
{
private final long randomSeed;

private final long prime0;
private final long prime1;

public UndoableShuffle()
{
this(System.nanoTime());
}
public UndoableShuffle(long randomSeed)
{
this.randomSeed = randomSeed;

Random random = new Random(randomSeed);
prime0 = BigInteger.probablePrime(48, random).longValue();
prime1 = BigInteger.probablePrime(48, random).longValue();
}

private int getPseudorandomIndex(int counter, int max)
{
long value = counter + randomSeed;
value *= prime0;
value += prime1;
value &= ((1L << 48) - 1);
return (int)(value % max);
}

public <T> void apply(List<T> list)
{
for (int i=0; i<list.size(); i++)
{
int j = getPseudorandomIndex(i, list.size());
swap(list, i, j);
}
}

public <T> void undo(List<T> list)
{
for (int i=list.size()-1; i>=0; i--)
{
int j = getPseudorandomIndex(i, list.size());
swap(list, j, i);
}
}

private static <T> void swap(List<T> list, int i, int j)
{
list.set(i, list.set(j, list.get(i)));
}


}

public class UndoableShuffleTest
{
public static void main(String[] args)
{
List<String> list = new ArrayList<String>();
list.addAll(Arrays.asList("A", "B", "C", "D", "E"));

System.out.println("Initial list : "+list);

UndoableShuffle undoableShuffle = new UndoableShuffle();
undoableShuffle.apply(list);

System.out.println("After shuffle: "+list);

undoableShuffle.undo(list);

System.out.println("After undo : "+list);
}


}
28.06.2012
Marco13 286 1 2

Stelle deine Java-Frage jetzt!