Möglichkeiten aufliste - Wie?

[Gast]

Hallo,

ich habe folgendes Problem ???:L :

 0 0 0 0
 ...
 2 2 2 2
----------------------------------------------------------
 3*3*3*3 Möglichkeiten = 3^4 = 81 Kombinationsmöglichkeiten

An jeder Stelle (1,2,3 oder 4) kann eine 0, 1 oder 2 stehen. Nun möchte ich ein Javaprogramm haben, dass mir zunächst alle Möglichkeiten generiert (und später auf n-Stellen verallgemeinert wird).

Lösungen wären:

1. 0000
2. 1000
3. 2000
4. 0100
5. 0200
6. 0010
7. 0020
...

Wie programmiert man soetwas am besten (mit einer großen for-Schleife??)?

Gast :bahnhof:

 

[Leroy42]

Wie programmiert man soetwas am besten (mit einer großen for-Schleife??)?

Kombination aus (simpler) For-Schleife und Rekursion wäre angebrachter!

 

[ARadauer]

mit verschachtelten for schleifen

   public static void main(String[] args) {
      for(int i = 0; i <4; i++){
         for(int j =0; j<4;j++){
            for(int k = 0; k<4;k++){
               for(int l = 0; l <4; l++){
                  System.out.println(i+" "+j+" "+k+" "+l);
               }
            }
         }
      }
   }

 

[mikachu]

Das sieht mir sehr nach Permutation aus.

Hab da hier was gefunden.

#edit 1:
Ne, war ein falscher Gedanke... hab sehr lange nix mehr mit Java zu tun gehabt ;-)

 

[Gast]

mit verschachtelten for schleifen

   public static void main(String[] args) {
      for(int i = 0; i <4; i++){
         for(int j =0; j<4;j++){
            for(int k = 0; k<4;k++){
               for(int l = 0; l <4; l++){
                  System.out.println(i+" "+j+" "+k+" "+l);
               }
            }
         }
      }
   }

Diese Möglichkeit ist möglich, kann ich aber leider nicht benutzen, da ich ja die Methode auf n (Länge) veralgemeinern möchte!

Ich denke - wie auch Leroy42 -, dass ich dafür eine Rekursion benötige:
Man geht das Ganze durch mit einer for-Schleife und ruft bei jedem Schritt der for-Schleife 3 mal die Methode auf (mit 0, 1 und 2). Doch leider hab ich keine Ahnung, wie ich das in Code umsetzten soll!

Gast :bahnhof: :bahnhof:

 

[SlaterB]

tja, ohne Idee kein Programm, so einfach,
versuche dich an einfacheren Rekursionen, z.B. Fakultät, eine Liste oder ein Array durchlaufen, oder einen String der Länge k zusammenbauen,
wenn das auch nicht geht, dann muss unbedingt erstmal ein Lehrbuch mit Beispielen her,
wenn das doch geht, dann poste mal entsprechendes, vielleicht läßt sich das erweitern

-----

es gibt auch noch eine nicht-rekursive Möglichkeit,
quasi der iterative Nachbau der Rekursion

erstelle dir ein Array der Länge n, initialisiere es mit
0 0 0 0
und zähle das in eine Endlosschleife hoch
0 0 0 1
0 0 0 2
0 0 1 0
0 0 1 1
0 0 1 2
usw.
pro Schleifendurchgang den aktuellen Wert anschauen und den Nachfolger errechnen, so wie Schuladdition mit Übertrag

Abbruch nach
2 2 2 2

 

[mikachu]

...Doch leider hab ich keine Ahnung, wie ich das in Code umsetzten soll!

Gast :bahnhof: :bahnhof:

Programmieren besteht nunmal zu 90% aus theoretischen Aufgaben wie Analyse, Konzepte finden, Lösungen vorschlagen, Algorithmus entwerfen... und eben nur zu 10% aus dem eigentlichen Programmieren

Alle wollen immer gleich drauflos tippsen, ohne sich erstmal Gedanken zu machen, WIE das Ziel denn erreicht werden soll.

Ging/Geht mir aber auch so :### :meld:

 

[Landei]

Wie würdest du das ganze programmieren, wenn die Zahlen von 0 bis 9 gehen würden? Richtig, einfach hochzählen (evtl. dann die Zahl rückwärts ausgeben, je nach Geschmack).
Die einfachste Lösung ist also, einfach eine Zahl hochzuzählen und sie im 3-er System (mit den Ziffern 0..2) auszugeben. Ohne jetzt auf Reihenfolge, richtigen Endwert und Ausrichtung (führende Nullen) einzugehen - du sollst ja auch noch was machen - geht das so:

for (int i = 1; i < 4711; i++) {
  int k = i;
  while(k > 0){
     System.out.print(k % 3);
     k /= 3;
  }
  System.out.println();
}

 

[Wildcard]

Wie Landei sagt, einfach hochzählen. Danach dann mit Integer.toString(zahl, radix) arbeiten.

 

[Gast]

Gibt es in Java einen Befehl, der z.B. dem PHP-Befehl "eval" nahe kommt? Könnte man dann nicht einfach die for-Schleifen als String erzeugen und mit eval ausfüren?

Gast

 

[Wildcard]

Nein. Warum willst du die for-Schleife erzeugen, statt einfach zu schreiben?

 

[SlaterB]

weil die Anzahl der verschachtelten Schleifen von einem Parameter n abhängt

dabei gibts hier so viele schönere Ideen

 

[Wildcard]

Warum? Einfach hochzählen wie gesagt. Man braucht genau eine Schleife.

 

[Leroy42]

Richtig!

Aber schön ist das eigentlich nicht

 

[Wildcard]

Aber schön ist das eigentlich nicht

Warum? ???:L

 

[Leroy42]

Aber schön ist das eigentlich nicht

Warum? ???:L

Rekursion ist geiler

 

[Marco13]

Gibt es in Java einen Befehl, der z.B. dem PHP-Befehl "eval" nahe kommt? Könnte man dann nicht einfach die for-Schleifen als String erzeugen und mit eval ausfüren?

Einen Befehl gibt es nicht, aber seit Java 1.6 eine "Compiler"-Funktionalität, mit der man das machen könnte. Aber DAS wäre wirklich nicht schön.

 

[Leroy42]

aber seit Java 1.6 eine "Compiler"-Funktionalität, mit der man das machen könnte.

Was meinst du?

 

[Guest]

mal ganz ohne schleifen, dafür rekursiv,

aber ob das schöner/ geiler ist?!?

public class Kombinator {
	
	private static final int erster = 'a';
	private static final String BACKSPACE = "\b";
	
	/**
	 * 
	 * @param anfang der string der bisher zusammengefrikelt wurde
	 * @param laenge wie lange das ganze noch zusammengefrikelt werden soll
	 * @param moeglichkeiten welche möglichkeiten angeboten werden sollen
	 * @param aktueller was momentan an das bisher zusammengefrikelte dazugefrikelt werden soll
	 */
	public static void kombiniere(String anfang, int laenge,
			int moeglichkeiten, int aktueller) {
		if (laenge == 0) {
			System.out.print(anfang);
		} else {
			if (aktueller < erster + moeglichkeiten) {
				kombiniere(BACKSPACE+anfang + (char) aktueller, laenge - 1,
						moeglichkeiten, erster);
				kombiniere(anfang, laenge, moeglichkeiten, aktueller + 1);
			}
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		kombiniere("", 3, 3, erster);
	}
}

:?:

 

[SlaterB]

das vielleicht nicht, aber wie wärs mit

public class Test
{

    /**
     * 
     * @param builder
     *            der string der bisher zusammengefrikelt wurde
     * @param laenge
     *            wie lange das ganze noch zusammengefrikelt werden soll
     * @param moeglichkeiten
     *            welche möglichkeiten angeboten werden sollen
     */
    public static void kombiniere(StringBuilder builder, int laenge, int moeglichkeiten)
    {
        if (laenge == builder.length())
        {
            System.out.println(builder);
            return;
        }
        for (int i = 0; i < moeglichkeiten; i++)
        {
            builder.append(i);
            kombiniere(builder, laenge, moeglichkeiten);
            builder.setLength(builder.length() - 1);
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args)
    {
        kombiniere(new StringBuilder(), 2, 4);
    }

}

 

[Gast]

hm, dafür aber wieder mit schleife

 

[SlaterB]

eine Schleife ist ja nichts schlechtes, nur n Schleifen kann man halt nicht passend bauen
(außer mit String-Zusammenbau und dann Compiler anschmeißen )

die Rekursion erlaubt auf elegante Weise, die Anzahl der Schleifen zu bestimmen

 

[Gast]

Vielen, vielen Dank !!! :applaus:

Jetzt verstehe ich auch, wie das funktioniert!! Kann man den Stringbuilder auch durch einen ganz normalen String ersetzen? Wo liegt der Vorteil von einem StringBuilder?

Gast :toll:

 

[SlaterB]

es dauert nicht x mal so lange, je nach Pech

String + String erzeugt immer einen neuen String, ein StringBuilder ist humaner, verwaltet ein großes char-Array, ich welches nur neue Zeichen eingefügt werden

für kleine Programme unter 100.000 Kombinationen ist das relativ egal, da kannst du auch String nehmen

 

[Gast]

...
    public static void kombiniere(String builder, int aktuelleLaenge , int laenge, int moeglichkeiten)
    {
        if (laenge == aktuelleLaenge)
        {
            System.out.println(builder);
            return;
        }
        for (int i = 0; i < moeglichkeiten; i++)
        {
            builder = builder + i + "";
            kombiniere(builder, laenge, moeglichkeiten);
            aktuelleLaenge--;
        }
    }
...

So müsste das doch mit einem String funktionieren, oder?

 

[SlaterB]

bisschen denken wäre schon nützlich, welchen Sinn soll
> aktuelleLaenge--;
haben? die Variable aktuelleLaenge wird doch nirgendwo mehr benutzt,

und wenn die Methode 4 Parameter hat, dann muss man auch immer 4 übergeben,
aber aktuelleLaenge kann wohl komplett wegfallen

----

außerdem wird der builder-String immer länger, aber nicht wieder kürzer,
günstigerweise muss man builder in diesem Fall gar nicht ändern, es geht


if (laenge == builder.length())
{
System.out.println(builder);
return;
}


for (int i = 0; i < moeglichkeiten; i++)
{
kombiniere(builder+i, laenge, moeglichkeiten);
}