Elemente eines Arrays mischen

[Thorsten]

Hallo

Ich hab mal ne kleine Herausforderung für alle:

Ich suche eine Möglichkeit, ein Array zu mischen,
und wieder zurück zu sortieren -- mit Hilfe der
Mathematik.

Also ein Array so richtig gut durchwürfeln, aber
halt berechenbar -- um es wieder zurück zu bekommen.

Folgendes Szenario:
===================
Ich habe ein Array, dass gemischt werden soll. Danach
wird es auf die Festplatte geschrieben. Nun soll es
irgendwann wieder geladen werden, und in seinen originalen
Zustand zurück finden...

Das muss alles gehen, ohne ein extra Array auf die Festplatte
zu schreiben!

Infos:
======
Zur Verfügung steht: Das Eingabearray in der Form int[] mit
sehr vielen Einträgen... geht in die Millionen. 8)

Dann ein Array mit festen Werten (byte[]). Das ist etwa 20
Einträge lang. Dieses Array muss auch benutzt werden.
Es kann auch später noch eindeutig einem großen Array zugeordnet
werden.

Das war es. Damit muss man auskommen. Man kann natürlich
alle normalen mathematischen Funktionen benutzen, wie cos,
sin, exp und so weiter...

Bedingungen:
============
Es sollte in endlicher Zeit zum Ergebnis führen. :wink: Also sagen wir
mal bis zu einer Sekunde für eine Millionen Einträge im Hauptarray!
So in der Art... darf also keine Minuten dauern...

Das Hauptarray soll aber nicht nur einfach um x Einträge
verschoben werden. Also jeden Eintrag um x Positionen verschieben.
Das ist zu einfach!

Und die Arrays dürfen auch nicht vergrößert werden.


Meine eigene Idee:
===================
Die beste Lösung geht wohl leider nicht:
Ich würde am liebsten alle Einträge im Hauptarray einfach nach dem
Wert sortieren. Die niedrigsten alle nach links, die höhsten weit nach
rechts.

Das wäre die beste Lösung -- für mich!

Aber wie will man dann die Positionen der Werte rekonstruieren? Ja,
man braucht ein zweites Array, wo die Positionen drinne sind. Aber
wenn das Hauptarray 5 Millionen Einträge hat, muss man 10 Millionen
auf die Festplatte schreiben. Die Dateien werden mir einfach zu groß! :shock:

Mir fällt einfach nichts gutes ein

 

[Reality]

Zum Mischen erzeugst du Zufallszahlen. Die zufällig erzeugten Zahlen kannst du ja zur Widerherstellung speichern.

Liebe Grüße
Reality

 

[Thorsten]

Das geht doch auch nicht:
Ich müsste eine Losung (wie beim Lotto) durchführen -- im Prinzip.

Also:
In einer Schleife liefert mir ein Randomizer Zahlen. Wenn er eine
hat, die im Bereich des Hauptarrays liegt, muss diese Zahl aus
der Liste gelöscht werden. Damit sie kein 2. mal benutzt wird.

Und so wird es am Ende sehr lange dauern, bis er die letzten
"gezogen" hat :wink:

Oder hab ich einen Denkfehler? ???:L

 

[bygones]

verwandel den Array temporär in eine Liste über Arrays.asList(array) und dann kannst du über das Collection Framework einmal Collections.shuffle(list) die Liste durchwühlen und dann per Collections.sort(list) sortieren. und wenn du willst kannst du dann wieder per list.toArray() das Ganze in einen Array umwandlen ....

meinst du sowas ?

 

[Isaac]

Wenn ich ihn richtig verstanden habe will er die Liste zwar randomizen aber eben aufgrund einer mathematischen Funktion. Also z.b. aus der Position und des Wertes eines int im Array. Um dann später, wenn das Array wieder zurück gelesen wird die Ausgangslage wieder her zustellen indem die Funktion einfach umgekehrt wird.

Ist aber nicht ganz trivial das ganze. Wenn es denn ohne Metadaten zu erzeugen überhaubt möglich ist.

 

[Thorsten]

Also... ich hab jetzt ne Lösung Ich habe die Frage in 4 Foren gestellt :wink:
Da das andere Forum kein Partner-Forum von diesem ist, kopiere ich mal nur
den Code:

public class bla
{
	static String bla = "abcd";
   	static byte[] blub = bla.getBytes();
   	static int last;
	
   public static void main (String [] args)
   {
      int [] array= new int[15];
      
      for(int i = 0 ; i < array.length ; ++i) array[i] = i;
      System.out.println("Original:");
      printArray(array);
      shuffle(array);
      System.out.println("gemischt:");
      printArray(array);
      reShuffle(array);
      System.out.println("Wiederhergestellt:");
      printArray(array);
   }
   
   public static void printArray(int[] array)
   {
      for(int i = 0 ; i < array.length ; ++i)
      {
         System.out.print(array[i] + "  ");
      }
      System.out.println();
   }
   
   public static void shuffle(int [] array)
   {  	
   	  int counter = -1;
      for(int i = array.length - 1; i > 0 ; --i)
      {
      	
      	if (++counter == blub.length)
      	{
      		counter = 0;
      	}
      	
         int swapIndex = getSwapIndex(array.length,i,blub[counter]);
         int temp = array[swapIndex];
         array[swapIndex] = array[i];
         array[i] = temp;
      }
      
      last = counter;
   }
   
   public static void reShuffle(int [] array)
   {
   	  //Fehler
   	  //bla = "abce";
   	  //blub = bla.getBytes();
   	
   	  int counter = last + 1;
      for(int i = 1 ; i <  array.length ; ++i)
      {
      	
      	 if (--counter == -1)
      	 {
      	 	counter = blub.length - 1;
      	 }
      	
         int swapIndex = getSwapIndex(array.length,i,blub[counter]);
         int temp = array[swapIndex];
         array[swapIndex] = array[i];
         array[i] = temp;
      }
   }
   
   public static int getSwapIndex(int numberOfSwaps, int currentSwap, byte bla)
   {
      double temp = StrictMath.sin(1/(0.0005 + currentSwap * (0.1 / ( (double)numberOfSwaps + (bla*100 )) )));
      temp = StrictMath.abs(temp);
      return (int)StrictMath.round(temp*(double)currentSwap);
   }
}

Der springende Punkt ist die Gleichung y = sin(1/x) Funktioniert perfekt :shock: Besser, als ich dachte.
Wenn mein Programm für'n Beta-Test bereit ist, werdet ihr sehen, wozu das Ganze :wink: