Zufallsstrings erstellen (Java)

[pGRoBkiLL]

Hi,
also die Überschrift passt nicht wirklich aber mir ist nichts anderes eingefallen.
Folgendes Problem :

Ich habe eine Zeichenpool p = {'a', 'b', 'c', 'd'}
Nun will ich z.b. Strings der Länge 3 aus den Zeichen aus diesem Pool erstellen.
Ich will jedoch alle Möglichkeiten haben, die es gibt.
Bsp.: aaa,aab,aac,aad, aba, ... , ddd
Diese würde ich dann z.b. in eine ArrayList schreiben. In dem Fall wären das nun 64 Möglichkeiten.
Ich würde es nun mit 3 For-Schleifen probieren.
Das Problem ist jedoch, dass die Länge der Strings nicht vorgegeben ist. Das ganze soll also für jede Länge funktionieren. Wenn ich also Strings der Länge 10 will, müsste ich 10 For-Schleifen ineinander schachteln. Das wäre ziemlich doof.
Jemand eine Idee, wie ich dieses Problem eleganter und vor allem einfacher lösen kann ?

 

[RRA^StArFiRe]

geht eigentlich nur mitm baumschema.

also n root mitm array[|p|] und string='' und jedes element verweist auf ne node mit auch jeweils array[|p|] mit jeweils den strings='p[x]'

usw. bis du die länge hast.

aufzubauen wär der dann so:

---------------------------------

private root;

public class node{
node[] arr = array[|p|];
String str ='';

node()
{
}

public node(int depth)
{
  for i=0 bis |p|  
  this.arr[i]= new node(depth-1, i);
}

public node(int depth, int platz)
{
 this.String = p[platz];
 if(depth >1)
  for i=0 bis |p|  
   this.arr[i]= new node(depth-1, i);
 else
   for i=0 bis |p|  
    this.arr[i]= null;
}

}

}

main()
root = new node(depth);

---------------------------------

jetz haste also nen baum von der größe deiner gewünschten länge.
und in jedem knoten steht n buchstabe.
ganz linker pfad also aaa und ganz rechter pfad ddd.
jetzt musste die nur noch einsammeln.
rekursionen fürs durchlaufen von bäumen findest ja überall.
also sammelst immer die chars von den knoten ein.
wenn du an ein blatt gelangst, schreibste das ergebnis in dein array und setzt den zeiger dafür eins hoch.
und für jeden schritt den du zurückgehst, schneidest den letzten buchstaben vom gesammelten string ab.

 

[Clawg]

Denke umgekehrt

Am Ende hast du ElementZahl hoch StringLaenge verschiedene Strings. Auf diese Anzahl verschiedener Strings kann man ueber einen Index zugreifen, naemlich 'Element an Stelle 0' + 'Element an Stelle 1' * 'Zahl verschiedener Elemente' + 'Element an Stelle 2' * 'Zahl verschiedener Elemente' hoch 2 + usw.
Die Funktion kann man auch umdrehen und direkt abfragen, wie der String an einem Index aussaehe, indem man jeweils Index modulo ElementZahl nimmt, das Ergebnis in ein Zeichen entsprechend dem Elementpool speichert und den Index durch Elementzahl ganzzahlig teilt bis er 0 ist. Damit haettest du eine Funktion die einen Index in einen gewuenschten String wandelt, du musst dann nur noch eine einzelne For-Schleife machen, die alle Werte bis ElementZahl hoch StringLaenge der Funktion uebergibt.

edit:
Bzw. wenn dir die Zugriffszeit egal oder der Speicherplatz zu gering ist, rufst du einfach die Funktion mit entsprechendem Index (z.B. eine Zufallszahl) auf, wenn du einen String benoetigst.

@=Starfire=:
Nein, geht einfacher auch ohne Baum, weil man die Abstaende zwischen den Aesten genau kennt.

 

[RRA^StArFiRe]

oder machst es halt ohne baum, aber mit selben rekursionsschema

string[] deinarray= string[bla] 

public node(int depth, int platz, string str)
{
 if(depth >0)
  for i=0 bis |p|  
   node(depth-1, i, str++p[platz]);
 else
    deinarray.push(str++p[platz]);
}

kA, obs push gibt. an nächste freie stelle vom array packen halt.

 

[pGRoBkiLL]

Naja habs jetzt genauso gemacht.

public static void generateStr_rek(int wortlaenge, String str){
		
		for(int i=0;i<p.length;i++){
			if(wortlaenge == 0){
				al.add(str+p[i]);
			}
			else{
				generateStr_rek(wortlaenge-1,str+p[i]);
			}
		}
	}

Problem ist nun : Mein Pool umfasst 94 Zeichen, somit krieg ich nach paar Sekunden java.lang.OutofMemoryError: Java Heap Space


Arrrgh ich werd noch wahnsinnig.

 

[4GT_DosX]

Man könnte das Array mit einer Codierung versehen und diese dann stellenweise mit System erhöhen und als Index für das Chararray nutzen.

Codierung zB:
0000 => [0][0][0][0] => aaaa
2102 => [2][1][0][2] => cbac
(Indexnummer entspricht dem Code)

Geht natürlich auch anders, aber so braucht man weniger Schleifen.

 

[EnimaN]

Original geschrieben von [pG]RoBkiLL
Naja habs jetzt genauso gemacht.

public static void generateStr_rek(int wortlaenge, String str){
		
		for(int i=0;i<p.length;i++){
			if(wortlaenge == 0){
				al.add(str+p[i]);
			}
			else{
				generateStr_rek(wortlaenge-1,str+p[i]);
			}
		}
	}

Problem ist nun : Mein Pool umfasst 94 Zeichen, somit krieg ich nach paar Sekunden java.lang.OutofMemoryError: Java Heap Space


Arrrgh ich werd noch wahnsinnig.

und das wundert dich? 4 ^ 94 ist allein schon größer 10^56. omg ich glaube du hast entweder die aufgabe falsch verstanden, oder eurer professor verarscht euch.

 

[Busta_inaktiv]

Original geschrieben von [pG]RoBkiLL
Problem ist nun : Mein Pool umfasst 94 Zeichen, somit krieg ich nach paar Sekunden java.lang.OutofMemoryError: Java Heap Space

wtf, alle Kombinationen aus 94 Zeichen?

Nun verrat uns endlich wofür der Quatsch gebraucht wird, es gibt sicherlich einen sinnvolleren Weg.

 

[pGRoBkiLL]

Naja es sind 94^3 in meinem Fall. Was noch im Rahmen des möglichen ist. Um die Aufgabe zu lösen klappt meine Methode mit den 3 Schleifen ohne Rekursion bestens.
Ich will das ganze nur etwas allgemeiner fassen und darum such ich möglichkeiten ohne n Schleifen.

 

[Clawg]

Werde ich ignoriert oder war mein Text unverstaendlich?

@4GT_DosX:
Ja, das war mein Vorschlag. Allerdings wuerde ich ein eindimensionales Array nehmen und den genauen Index von Hand berechnen.
mein_array[z][y][x]
mein_array[x + y * MAX_ELEMENTS + z * MAX_ELEMENTS * MAX_ELEMENTS]

 

[4GT_DosX]

Das war auch eigentlich für ein eindimensionales Array gedacht.
Hab deins noch nicht gelesen gehabt, weil ich die Idee erstmal anprogrammiert und dann zusammengefasst hab.

 

[pGRoBkiLL]

Also ich habs nicht wirklich verstanden was du sagen wolltest. Aber macht nix, habs jetzt per Rekursion und ohne Speicherung sondern mit direkter Überprüfung gemacht. Somit läuft der Speicher auch nicht über.
Für alle Interessierten.
Aufgabe war, ein Programm zu schreiben, welches ein mit crypt(3) verschlüsseltes Passwort entschlüsselt.