Viele verschachtelte Schleifen

[minimammut]

Hallo allerseits,
ich habe ein Problem, dass ich sehr viele (8) gleichartige Schleifen ineinander geschachtelt habe. Das sieht ungefähr so aus:

...
for(int c=0;c<27;c++){
  z[6]=c;
  for(int b=0;b<27;b++){
    z[7]=b;
    for(int a =0;a<27;a++){
      z[8]=a;
      zahlen.add(z);
    }
  }
}
...

Was ich machen will ist sozusagen hochzählen zur Basis 26.
Das müsste ja auch so funktionieren, nur dachte ich mir, dass es doch nicht wahr sein kann, dass man 8 mal fast das gleiche schreiben muss. Gibt es für das Problem eine deutlich bessere Lösung?
Und allgemein, gibt es etwas, mit dem man einfach geschachtelte Schleifen leichter angeben kann, sozusagen eine "Potenzschleife?".
Eine rekursive Lösung hab ich auch schon geschrieben, ab 6 Stellen reichte jedoch leider der Speicher nicht.
Freue mich über alle Anregungen,
Gruß minimammut

 

[0x7F800000]

Was ich machen will ist sozusagen hochzählen zur Basis 26.

Das problem ist mir nicht klar. Was soll das bedeuten "zur Basis hochzählen"? Man kann entweder zählen ( =bijektive Abbildung zur menge der natürlichen Zahlen angeben) oder eine natürliche Zahl bezüglich einer Basis darstellen (praktisch zeichenkette hinschreiben)

Was willst du denn? Irgendwelche Kombinationen einer 27-elementigen Menge durchprobieren? Ist dir bewusst, dass da zwölfstellige Zahlen rauskommen können?

 

[minimammut]

ich möchte dass ich am ende alle höchstens acht stelligen Zahlen im "26er System" gesammelt habe. Also 0 0 0 0 0 0 0 0 bis 26 26 26 26 26 26 26 26

 

[faetzminator]

Und warum machst du da nicht nur eine Schleife? Ist mathematisch ein Bisschen komplexer aber sollte sogar lesbarer sein.

 

[Marco13]

Jup, da isses wieder 😉

Diesmal? Passwortcracken 🙂

Am einfachsten ist das rekursiv:

public boolean increase(int array[], int index, int maxValue)
{
    if (index==-1) return false;
    if (array[index]==maxValue)
    {
        array[index] = 0;
        increase(array, index-1, maxValue);
    }
    else
    {
        array[index]++;
    }
    return true;
}

Aufruf mit
[c]
increase(array, array.length-1, 26);
[/c]

Immer denselben Array zu "zahlen" hinzuzufügen ist übrigens witzlos.
[c]
zahlen.add(z.clone());
[/c]
wäre vermutlich sinnvoller. Wobei du dafür nicht genug RAM haben dürftest. Aber das nur nebenbei.

 

[0x7F800000]

ich möchte dass ich am ende alle höchstens acht stelligen Zahlen im "26er System" gesammelt habe. Also 0 0 0 0 0 0 0 0 bis 26 26 26 26 26 26 26 26

Geht nicht. Hier war neulich einer, wollte auch Milliarde von Milliarden int-Arrays anlegen. Ich habe kurz nachgerechnet: dazu bräuchte er einen 20x20x20 Meter großen würfel aus den teuersten festplatten, die es momentan auf dem markt gibt. In deinem Fall wäre das "nur" ein 20x20x5 meter großer Quader^^
Mach das was Marco13 ungefähr skizziert hat, aber denk nicht mal dran, diesen Kram abzuspeichern, das brauchst du nicht mal, wenn es tatsächlich um Passwörter geht.

Und nur so nebenbei: du rechnest im 27'er system...

 

[Shulyn]

ich möchte dass ich am ende alle höchstens acht stelligen Zahlen im "26er System" gesammelt habe. Also 0 0 0 0 0 0 0 0 bis 26 26 26 26 26 26 26 26

2417851639229258349412352 x 8 stellen im Array Speichern :shock:


// ich geh mir erstmal einen Kaffee zapfen


OK wieder da, was meinst du mit "gesammelt habe" ? Sie wirklich zu Speichern ??

 

[moormaster]

Ich würde sowas nicht iterativ mit verschachtelten Schleifen lösen und rekursiv schon gar nicht.

Ich würde die aktuelle Zahl einfach in einem Array bestehend aus 8 Elementen (die Zahl soll ja aus 8 Stellen bestehen) speichern und mir dann eine Funktion bauen, welche mir zu einer solchen Zahl den Nachfolger ausrechnet:

 public class Number
 {
  int base;

  // value[0] * base^0 + value[1] * base^1 + ...
  int[] value;

  public Number(int base, int length)
  {
   this.base = base;
   this.value = new int[length];
  }

 /*
  * returns true if overflow occured, false otherwise
  */
  public boolean calculateSuccessor()
  {
   int pos=0;
   boolean overflow = true;

   while (overflow && pos < value.length)
   {
    if (value[pos] < base-1)
     overflow = false;

    value[pos] = (value[pos] + 1)%base;
    pos++;
   }

   return overflow;
  }

  // ...
 }

Jetzt kannst du in einer einzelnen while Schleife immer calculateSuccessor() aufrufen und anhand des overflows erkennen, wann es wieder bei 0 0 0 ... losgeht 😀

 

[0x7F800000]

@moormaster: funktioniert es überhaupt, wenn ja: wie? hab's eben nicht hingekriegt... Eigene klassen nach den allergrundlegendsten Klassen der Core API zu benennen trägt jedenfalls nicht zur Übersicht bei.

@OP:
Für allgemeine Kombinationen von Elementen beliebiger endlicher Mengen kann man sowas benutzen:

//combinations as iterable
public static <T> Iterable<List<T>> getCombinations(final Collection<T> c, final int length){
	return new Iterable<List<T>>(){
		
		@Override
		public Iterator<List<T>> iterator() {
			
			return new Iterator<List<T>>(){
				private ArrayList<Iterator<T>> digitIterators=new ArrayList<Iterator<T>>(length);
				private ArrayList<T> next=new ArrayList<T>(length);
				boolean hasNext=c.size()>0 && length>0;
				{
					for(int i=0; i<length; i++){
						digitIterators.add(c.iterator());
						next.add(digitIterators.get(i).next());
					}
				}
				
				private boolean calculateNext(int digit){
					if(digit==length){
						return false;
					}else if(digitIterators.get(digit).hasNext()){
						next.set(digit,digitIterators.get(digit).next());
						return true;
					}else{
						digitIterators.set(digit,c.iterator());
						next.set(digit,digitIterators.get(digit).next());
						return calculateNext(digit+1);
					}
				}
				
				@Override
				public boolean hasNext(){
					return hasNext;
				}
				
				@Override
				public List<T> next(){
					List<T> temp=new ArrayList<T>(next);
					hasNext=calculateNext(0);
					return temp;
				}
				
				@Override
				public void remove(){
					throw new UnsupportedOperationException("w'the fuck?");
				}
			};
		}
	};
}

Beispiel:

Collection<Character> c=new LinkedList<Character>();
for(char x='0'; x<='9'; x++){
	c.add(x);
}

for(List<Character> combi:getCombinations(c,3)){
	System.out.println(combi);
}

Kannst dich natürlich davon (oder von Marco13's kürzeren version) inspirieren lassen, um dasselbe speziell für integer-arrays zu schreiben.

 

[moormaster]

@moormaster: funktioniert es überhaupt, wenn ja: wie? hab's eben nicht hingekriegt... Eigene klassen nach den allergrundlegendsten Klassen der Core API zu benennen trägt jedenfalls nicht zur Übersicht bei.

Dann nenn sie halt anders... ob dieses Beispiel funktioniert, weiss ich nicht; habs nicht compiliert 😀 Aber das Prinzip funktioniert auf jeden Fall... Addition mit Übertrag; mehr ist das nicht, was ich dort gemacht hab.

 

[Marco13]

@Moormaster: Die Rekursion geht nur bis maximal Tiefe 8, das ist wohl noch OK - aber sie ist auch, wie du geschrieben hast, sehr einfach in eine While-Schleife zu ändern.

Ganz nebenbei, und wie Andrey schon indirekt angedeutet hat, ist das ein Problem, das auch mit http://www.java-forum.org/codeschnipsel-u-projekte/81973-combinatorics.html gelöst werden könnte - allerdings dort wegen der Allgemeingültigkeit nur mit Integer statt mit int.

 

[Ariol]

Warum denn so kompliziert? Es soll doc nur gezählt werden:

import java.awt.Container;
import java.util.ArrayList;
import java.util.Arrays;

public class Main
{
	private static int	employeeCount;


	static ArrayList<String> stringZahlen = new ArrayList<String>();
	static ArrayList<int[]> zahlen = new ArrayList<int[]>();
	
	public static void main(String[] args)
	{
		int positions = 2;
		for(long i = 0; i < Math.pow(26, positions); i++)
		{
			stringZahlen.add(Long.toString(i, 26));
		}
		
		for(String zahl: stringZahlen)
		{
			int[] zArray = new int[zahl.length()];
			for(int i = 0; i < zahl.length(); i++)
			{
				char c = zahl.charAt(i);
				int val = c<0x3a?c-0x30:c-0x61+10; //convert from ascii
				zArray[i] = val; 
			}
			zahlen.add(zArray);
		}
		
		for(int[] zahl : zahlen)
		{
			for(int i = 0; i < zahl.length; i++)
			{
				System.out.print(zahl[i] + "\t");
			}
			System.out.println();
		}
		
	}
}import java.awt.Container;
import java.util.ArrayList;
import java.util.Arrays;

public class Main
{
	private static int	employeeCount;


	static ArrayList<String> stringZahlen = new ArrayList<String>();
	static ArrayList<int[]> zahlen = new ArrayList<int[]>();
	
	public static void main(String[] args)
	{
		int positions = 2;
		for(long i = 0; i < Math.pow(26, positions); i++)
		{
			stringZahlen.add(Long.toString(i, 26));
		}
		
		for(String zahl: stringZahlen)
		{
			int[] zArray = new int[zahl.length()];
			for(int i = 0; i < zahl.length(); i++)
			{
				char c = zahl.charAt(i);
				int val = c<0x3a?c-0x30:c-0x61+10; //convert from ascii
				zArray[i] = val; 
			}
			zahlen.add(zArray);
		}
		
		for(int[] zahl : zahlen)
		{
			for(int i = 0; i < zahl.length; i++)
			{
				System.out.print(zahl[i] + "\t");
			}
			System.out.println();
		}
		
	}
}

Und da ist ne Menge Overhead bei.

 

[0x7F800000]

Und da ist ne Menge Overhead bei.

und alles doppelt gibt's ganz umsonst? :bahnhof:

Ich weiß jedenfalls nicht, was du da gemacht hast, aber für solche Stunts:

        for(long i = 0; i < Math.pow(26, positions); i++)
        {
            stringZahlen.add(Long.toString(i, 26));
        }

...benötigt man eben 20x20x5 meter quader aus Festplatten.

 

[Ariol]

und alles doppelt gibt's ganz umsonst? :bahnhof:

Ich weiß jedenfalls nicht, was du da gemacht hast, aber für solche Stunts:

        for(long i = 0; i < Math.pow(26, positions); i++)
        {
            stringZahlen.add(Long.toString(i, 26));
        }

...benötigt man eben 20x20x5 meter quader aus Festplatten.

Jop, aber das war doch nicht die Aufgabenstellung, oder?
minimammut will für eine bestimmte Anzahl an stellen alle möglichen Kombinationen von Zahlen zwischen 1 und 26. Das es dabei bei 9 Stellen (wie in seinem Beispiel-Code) 5429503678976 verschiedene Kombinationen gibt, und diese wohl etwas zu viel für seinen Speicher sind ist etwas anderes, dass er irgendwie sonst lösen muss:
Er benötigt mindestens 5Bit (26 verschiedene Zeichen) pro Position x 9 Positionen = 45Bit; 45bit x 5429503678976 Kombinationen = ca. 27,776839665 TB
Da aber dabei noch Dinge wie die Verwaltung der Daten fehlen und es keinen 5bit-Datentyp gibt wird es wohl doch eher das doppelte an Speicher werden.

Warum die Daten überhaupt gespeichert werden sollen ist auch nicht klar.

P.S.: so groß wird der Quader dann wohl doch nicht :wink:

 

[0x7F800000]

ca. 27,776839665 TB

Öööhm njum njam... :reflect:
Okay, deine schätzung sieht besser aus. Bei dieser Milliarde von milliarden Int-Array hab ich aber für eine preisgünstigere Lösung mit 80GB festplatten einen 30x30x30 meter würfel rausgekriegt... Kann auch sein, dass ich mich irgendwo verrechnet hab... 😳

50 TB passt jedenfalls nicht in den RAM. Und dass der OP Problem mit speicher hat, steht ja gleich im ersten Beitrag:

Eine rekursive Lösung hab ich auch schon geschrieben, ab 6 Stellen reichte jedoch leider der Speicher nicht.

Wenn er alles gleichzeitig im speicher haben will, bräuchte er also etwa 20000 mal soviel speicher. Das geht nicht. Die Lösung a' la Marco13 mit Iterables geht aber, weil dort die Kombinationen nicht im Raum, sondern in Zeit gespeichert werden. Zeit ist in diesem fall wesentlich billiger als Speicher.