Algorithmus für Kombinatorik?

Hallo, ich habe 5 Lampen, jeweils mit den möglichen Zuständen "an" und "aus".

Kann mir jemand bei der Beschreibung des Algorithmus helfen um alle "Beleuchtungskombinationen" auszugeben?

Also gerne in Pseudo-Code oder so. Ich blicke einfach nicht durch.

Habe es mit Schleifen versucht, aber bin direkt gescheitert.

Answer 1

[RakonDark]

lampe=new Array(0,0,0,0,0);
lampnr = 0; 
ueberlauf = false;
notende = true;
while (notende ) {
  ueberlauf = true;
  alert(lampe.join());
  while (ueberlauf) {
     if (lampe[lampnr] == 0) {
        lampe[lampnr] = 1;
       ueberlauf = false;
     } else {
       lampe[lampnr] = 0;
       ueberlauf = true;
       ++lampnr;
       if (lampnr == 5) {
          ueberlauf = false;
          notende = false;
       }
    }
  }
lampnr = 0;
}

in javascript ;)

Comments

[RakonDark]

optimierung ist immer gut

lampe=new Array(0,0,0,0,0);
lampnr = 0; 
ueberlauf = false;
notende = true;
while (notende ) 
{
   ueberlauf = true;
   alert(lampe.join());
   while (ueberlauf) 
   {
       if (lampe[lampnr] == 0) 
       {
          lampe[lampnr] = 1;
          ueberlauf = false;
       } 
       else 
       {
          lampe[lampnr] = 0;
          ++lampnr;
          if (lampnr == 5) 
          {
             ueberlauf = false;
             notende = false;
          }
       }
   }
   lampnr = 0;
}

[RakonDark]

@RakonDark

für x lampen

<script>
lampen = parseInt(prompt("Anzahl Lampen"));
lampe=new Array(lampen).fill(0);
lampnr = 0; 
ueberlauf = false;
notende = true;
while (notende ) 
{
   ueberlauf = true;
   alert(lampe.join());
   while (ueberlauf) 
   {
       if (lampe[lampnr] == 0) 
       {
          lampe[lampnr] = 1;
          ueberlauf = false;
       } 
       else 
       {
          lampe[lampnr] = 0;
          ++lampnr;
          if (lampe.length == lampnr) 
          {
             ueberlauf = false;
             notende = false;
          }
       }
   }
   lampnr = 0;
}  
</script>

Answer 2

[nobytree2]

Es ist wohl eine Permutation, also eine Baumstruktur, der nach unten kürzer wird. Bilde ein Array[5] mit boolean oder int oder ein binäres Konstrukt (geht aber nur bei 2 Zuständen gut, sonst Array besser).

Wichtige Schritte sind:

• Eine For-Schleife (Index, Index <= Elementanzahl, Index++)
• Ein Tausch auf Ebene des jeweiligen Index mit allen Elementen, die einen höheren Index haben
• Eine Rekusion in der Forschleife, wobei der Index erhöht wird, um die weiteren Elemente in einer Baumstruktur zu erreichen.
• Der Tausch muss dann immer wieder rückgängig gemacht werden.

Beispiel: Permutation von ABCDE: Zuerst wird das A durch alle Elemente B-C ersetzt, so dass an erster Position alle Buchstaben sind. Dabei ist jeweils (per Rekursion oder weiterer Schleife, das ist jedoch schwerer) für die folgenden Elemente dasselbe zu machen, also für die zweite Stelle von Axxxx, Bxxxx, Cxxxx, Dxxxx, Exxxx. Dann für die Dritte Stelle: ABxxx, ACxxx .... BAxxx, BCxxx, und auch für die dritte und vierte Stelle.

Bei nur zwei Zuständen kann man das leicht verkürzen, man sollte die Permutation aber insgesamt verstanden haben, z.B. wenn die Lampen 20 Zustände einnehmen können.

Woher ich das weiß: eigene Erfahrung – Hobby und teilweise beruflich

Answer 3

[Purphoros]

Im Grunde musst du einfach nur erklären, wie man zählt, aber binär. Stell dir vor, du würdest dein Fahrradschloss knacken, nur eben mit 0 und 1 anstatt 0 bis 9.

Erstmal der gewünschte Output: 

00000, 
00001, 
00010, 
00011, 
00100, 
00101, 
00110,
 ... 
11110, 
11111

Du hast hier nun 2 Möglichkeiten. 

Entweder, auch für Laien und Mathelehrer verständlich, du "zählst" die Kombinationen einfach durch. Dazu änderst du immer den Zustand der ganz rechten Lampe (aus wird an und an wird aus), und wenn eine Lampe ausgeschaltet wird, änderst du den Zustand der Lampe links daneben. Ganz so als ob du die Zehner erhöhst, wenn die Einser von 9 auf 0 springen.

Oder, so würde es ein (ineffizienter) Programmierer tun, du schachtelst 5 "for" Schleifen mit je 2 Durchläufen ineinander, die jeweils eine der Lampen ein- bzw. ausschalten. Beachte dabei, die innere Schleife vor dem Code der umfassenden Schleife auszuführen. 

soOftWie(möglicheZustände) //bei den Lampen sind das 2 Zustände
{
     soOftWie(möglicheZustände)
     {
          soOftWie(möglicheZustände)
          {
               soOftWie(möglicheZustände)
               {
                    soOftWie(möglicheZustände)
                    {
                         soOftWie(möglicheZustände)
                         {
                              Lampe5 umschalten
                         }
                         Lampe4 Umschalten
                    }
                    Lampe 3 Umschalten
          }
          Lampe 2 Umschalten
     }
     Lampe 1 Umschalten
}

Natürlich würde ein echter Programmierer dafur eine rekursive Methode schreiben, die mit einer beliebigen Anzahl Objekten mit einer beliebigen Anzahl Zuständen auskommt. Also, liebe Programmierer, bitte nicht flamen ;)

Comments

[Purphoros]

P.S. (Patchum Stupidum)

Ganz am Anfang jeder Schleife wird der Gesamtzustand an die Liste angefügt, das hatte ich vergessen und kann es leider nicht mehr reineditieren. Müsste so aussehen:

soOftWie(möglicheZustände) 
{
     alle Zustände ausgeben
     soOftWie(möglicheZustände)
     {
          alle Zustände ausgeben
          soOftWie(möglicheZustände)
...

Answer 4

[BaumeisterSepp]

Hier ist ein rekursiver Algorithmus, der die gewünschte Kombinatorik ermöglicht. Output für zB 3 Stellen:

000
001
010
011
100
101
110
111

public class BinaryPermutation {

  public static void main(String[] args) {
    binaryPermutation("", 3); 
  }

  public static void binaryPermutation(String digit, int iterations) {
    if(iterations == 0) {
      System.out.println(digit);
    } else {
      binaryPermutation(digit + "0", iterations - 1);
      binaryPermutation(digit + "1", iterations - 1);
    }
  }
}

Du kannst unter Angabe der "iterations" die Anzahl der Stellen definieren.
Also 5 für deine fünf Lampen.

Viele Grüße.

Comments

[BaumeisterSepp]

Den Algortihmus kannst du daraus ableiten. Grundidee: Rekursives füllen von 'digit' um 0 und 1 bis die Abbruchbedingung 'Anzahl der Iterationen' den Wert 0 erreicht. Jeder Durchlauf dekrementiert den Zähler und hängt je nach Durchlauf eine 0 oder 1 an.

Answer 5

[DrNumerus]

Du meinst die Anzahl der Möglichkeiten des gesammten, indem die einzelnen Lampen an- oder ausgeschaltet sein können?

In dem Fall musst du denken; du hast jeweils zwei möglichkeiten pro Lampe. Pro Möglichkeit der ersten Lampe, hast du Jeweils wieder zwei andere Möglichkeiten bei der Zweiten. (Wenn die erste an ist, kann die zweite an (1.) oder aus (2.) sein. Das gleiche auch für den Fall, dass die erste Lampe aus ist.) Also 2 Möglichkeiten mal 2 Möglichkeiten. Du hast je nach aktuelle Möglichkeit nun wieder zwei Möglichkeiten für die jeweils nächste Lampe.

Fazit:

Du hast jedes Mal wieder zwei Möglichkeiten pro Lampe die alle multipliziert werden. D.h.: n^L  (wobei L = Lampenanzahl und n = Anzahl der möglichen Zustände). Also 2^5 = 32 verschiedene Beleuchtungskombinationen.  

Das war wahrscheinlich ein typischer Fall von "zu kompliziert gedacht". Hab ich auch oft ;)

Woher ich das weiß: Studium / Ausbildung – Physik Studium - Master in theoretischer Physik

Comments

[Purphoros]

Hier geht es aber nicht nur um die Anzahl der Kombinationen, sondern darum, alle möglichen Kombinationen mit einem Algorithmus auszugeben. Im Grunde ein Programm, das alle möglichen Binärzahlen von 00000 bis 11111 ausgibt.

Ist wohl ein Fall von "zu schnell geschossen"...

[DrNumerus]

@Purphoros

Achso ich dachte es ginge hier um das mathematische "Prinzip". Tut mir leid, dann kann ich dir leider nicht weiter helfen. ^^